In a Wireless Mesh Network (WMN), the traffic is

aggregated and forwarded towards the gateways. Strategically

placing and connecting the gateways to the wired backbone is

critical to the management and efficient operation of a WMN.

In this paper, we address the problem of gateways placement,

consisting in placing a minimum number of gateways such that

QoS requirements are satisfied. We propose a polynomial time

near-optimal algorithm which recursively computes minimum

weighted Dominating Sets (DS), while consistently preserving

QoS requirements across iterations. We evaluate the

performance of our algorithm using both analysis and

simulation, and show that it outperforms other alternative

schemes by comparing the number of gateways placed in

different scenarios. -In　a Wireless Mesh Network (WMN), the traffic is

aggregated and forwarded towards the gateways. Strategically

placing　and connecting the gateways to the wired backbone is

critical to the management and efficient operation of a WMN.

In this paper, we address the problem of gateways placement,

consisting in placing a minimum number of gateways such that

QoS requirements are satisfied. We　propose　a　polynomial　time

near-optimal algorithm which recursively　computes　minimum

weighted　Dominating Sets (DS), while consistently preserving

QoS requirements across iterations. We evaluate the

performance of our algorithm using both analysis and

simulation, and show that it　outperforms other alternative

schemes by comparing the number of gateways placed　in

different scenarios.