TY - JOUR
T1 - PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
AU - Wu, Lidong
AU - Du, Hongwei
AU - Wu, Weili
AU - Zhu, Yuqing
AU - Wang, Ailan
AU - Lee, Wonjun
N1 - Funding Information:
This work was supported by National Natural Science Foundation of China with Grants 61100191 and 11071271, and Shenzhen Strategic Emerging Industries Program with Grants No. ZDSY20120613125016389 and No. JCYJ20120613151201451, and Natural Scientific Research Innovation Foundation of Harbin Institute of Technology under Project 2011128. This work was also supported in part by National Science Foundation of USA under Grants CNS101630 and CCF0829993. This research was also jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), MEST, Korea under Basic Science Research Program (2011-0012216), and MKE, Korea under ITRC NIPA-2011-(C1090-1121-0008).
Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2015/7/28
Y1 - 2015/7/28
N2 - 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 αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, mCDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and mCDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.
AB - 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 αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, mCDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and mCDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.
KW - Algorithm PTAS
KW - Growth bounded graphs
KW - Minimum connected dominating set
KW - Routing cost constraint
UR - http://www.scopus.com/inward/record.url?scp=84938213624&partnerID=8YFLogxK
U2 - 10.1007/s10878-013-9626-8
DO - 10.1007/s10878-013-9626-8
M3 - Article
AN - SCOPUS:84938213624
SN - 1382-6905
VL - 30
SP - 18
EP - 26
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 1
ER -
