Abstract
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 \(\alpha \) ROC–CDS where \(\alpha \ge 5\), that is, there exists a polynomial-time \((1+\varepsilon )\)-approximation for minimum CDS under constraint that for every pair of nodes u and v, \(m_{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_{CDS}(u,v)\) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J ACM 41: 153–180
Burkhart M, Rickenbach PV, Wattenhofer R, Zollinger A (2004) Does topology control reduce interference? In: Proceedings of the 5th ACM international symposium on mobile Ad Hoc networking and, computing, (MobiHoc04), pp 919
Ding L, Gao X, Wu W, Lee W, Zhu X, Du D-Z (2010) Distributed construction of connected dominating sets with minimum routing cost in wireless network. In: 30th international conference on distributed computing systems, ICDCS
Ding L, Weili W, Willson J, Du H, Lee W, Du D-Z (2011) Efficient algorithms for topology control problem with minimum routing constraints in wireless networks. IEEE Transact Parallel Distrib Syst 22(10):1601–1609
Du D-Z, Ko K-I, Hu X (2011) Design and analysis of approximation algorithms. Springer, New York
Du H, Wu W, Lee W, Liu Q, Zhang Z, Du D-Z (2011) On minimum submodular cover with submodular cost. J Glob Optim 50(2):229–234
Du H, Ye Q, Weili W, Deying L, Du D-Z, Howard S (2011) Constant approximation for virtual backbone construction with guarantee routing cost in wireless sensor networks, IEEE INFOCOM
Du H, Ye Q, Zhong J, Wang Y, Lee W, Park H (2012) Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks. Theor Comput Sci 447:38–43
Garey MR, Johnson DS (1978) A guide to the theory of NP-completeness. Computer and intractablity. Fressman, San Francisco
Gfeller B, Vicari E (2007) A faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs, Lecture Notes in Computer Science, vol 4686. Springer, Berlin, pp 57–74
Jain K, Padhye J, Padmanabhan VN, Liu LL (2005) Impact of interference on multi-hop wireless network performance. Wirel Netw 11:471–487
Kyasanur P, Vaidya NF (2005) Routing and interface assignment in multi-channel multi-interface wireless networks. In: Wireless communications and networking conference 2005 IEEE, vol 4, pp 2051–2056
Salem NB, Hubaux JP (2005) A fair scheduling for wireless mesh networks. In: The 1st IEEE workshop on wireless mesh networks, held in conjunction with SECON05, Santa Clara
Wan P-J, Du D-Z, Pardalos PM, Wu W (2010) Greedy approximation for minimum submodular cover with submodular cost. Comput Optim Appl 45(2):463–474
Willson J, Gao X, Qu Z, Zhu Y, Li Y, Wu W (2009) Efficient distributed algorithms for topology control problem with shortest path constraints. Discret Math Algorithm Appl 1(4):437–462
Acknowledgments
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).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, L., Du, H., Wu, W. et al. PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs. J Comb Optim 30, 18–26 (2015). https://doi.org/10.1007/s10878-013-9626-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9626-8