PTAS for the minimum weighted dominating set in growth bounded graphs

The minimum weighted dominating set (MWDS) problem is one of the classic NP-hard optimization problems in graph theory with applications in many fields such as wireless communication networks. MWDS in general graphs has been showed not to have polynomial-time constant-approximation if <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathcal{NP} \neq \mathcal{P}}$$</EquationSource> </InlineEquation> . Recently, several polynomial-time constant-approximation SCHEMES have been designed for MWDS in unit disk graphs. In this paper, using the local neighborhood-based scheme technique, we present a PTAS for MWDS in polynomial growth bounded graphs with bounded degree constraint. Copyright Springer Science+Business Media, LLC. 2012