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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{NP} \neq \mathcal{P}}$$\end{document} . 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.