PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Connected dominating set (CDS) has played an important role in building virtual backbone, which is used on unicast, multicast, and fault‐tolerant routing in wireless sensor networks. In order to reduce traffic congestion and communication delay, a routing‐cost constrained minimum CDS (ROC–CDS) has been studied extensively in the literature. In this paper, we present a PTAS for $\mathit{\alpha }$ ROC–CDS where $\mathit{\alpha }\ge 5$ , that is, there exists a polynomial‐time $(1+\mathit{ϵ})$ ‐approximation for minimum CDS under constraint that for every pair of nodes u and v, $m_{\mathit{CDS}}(u,v)\le m(u,v)$ where $m(u,v)$ denotes the number of intermediate nodes in the shortest path between u and v, and $m_{\mathit{CDS}}(u,v)$ denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.