Computing Minimum k-Connected m-Fold Dominating Set in General Graphs

References

• Bardossy MG, Raghavan S (2010) Dual-based local search for the connected facility location and related problems. INFORMS J. Comput. 22(4):584–602.Link, Google Scholar
• Bayati M, Kim JH, Saberi A (2010) A sequential algorithm for generating random graphs. Algorithmica 58(4):860–910.Crossref, Google Scholar
• Bondy JA, Murty USR (2008) Graph Theory (Springer, New York).Crossref, Google Scholar
• Carmesin J, Diestel R, Hamann M, Hundertmark F (2014a) k-blocks: A connectivity invariant for graphs. SIAM J. Discrete Math. 28(4):1876–1891.Crossref, Google Scholar
• Carmesin J, Diestel R, Hundertmark F, Stein M (2014b) Connectivity and tree structure in finite graphs. Combinatorica 34(1):11–46.Crossref, Google Scholar
• Cheng X, Huang X, Li D, Wu W, Du D-Z (2003) A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4):202–208.Crossref, Google Scholar
• Dai F, J Wu (2006) On constructing k-connected k-dominating set in wireless ad hoc and sensor networks. J. Parallel Distributed Comput. 66(7):947–958.Crossref, Google Scholar
• Das B, Bharghavan V (1997) Routing in ad-hoc networks using minimum connected dominating sets. Towards the Knowledge Millennium, IEEE Internat. Conf. Comm. (IEEE, New York), 376–380.Google Scholar
• Du D-Z, Wan P-J (2012) Connected Dominating Set: Theory and Applications (Springer, Berlin).Google Scholar
• Ephremides A, Wieselthier JE, Baker DJ (1987) A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. IEEE 75(1):56–73.Crossref, Google Scholar
• Fomin FV, Grandoni F, Kratsch D (2008) Solving connected dominating set faster than 2n. Algorithmica 52(2):153–166.Crossref, Google Scholar
• Fukunaga T (2015) Constant-approximation algorithms for highly connected multi-dominating sets in unit disk graphs. arXiv: 1511.09156.Google Scholar
• Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387.Crossref, Google Scholar
• Kleitman DJ, West DB (1991) Spanning trees with many leaves. SIAM J. Discrete Math. 4(1):99–106.Crossref, Google Scholar
• Li M, Wan P-J, Yao F (2009) Tighter approximation bounds for minimum CDS in wireless ad hoc networks. Dong Y, Du DZ, Ibarra O, eds. Algorithms and Computation (Springer, Berlin), 699–709.Google Scholar
• Li Y, Thai MT, Wang F, Yi C-W, Wan P-J, Du D-Z (2005) On greedy construction of connected dominating sets in wireless networks. Wireless Comm. Mobile Comput. 5(8):927–932.Crossref, Google Scholar
• Lu H-I, Ravi R (1992) The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. Proc. 30th Annual Allerton Conf. Comm. Control Comput. (University of Illinois, Urbana, IL), 533–542.Google Scholar
• Mader W (1978) Über n-fach zusammenhängende eckenmengen in graphen. J. Combin. Theory, Ser. B 25(1):74–93.Crossref, Google Scholar
• Robertson N, Seymour PD (1991) Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory, Ser. B 52(2):153–190.Crossref, Google Scholar
• Ruan L, Du H, Jia X, Wu W, Li Y, Ko K-I (2004) A greedy approximation for minimum connected dominating sets. Theoretical Comput. Sci. 329(1–3):325–330.Crossref, Google Scholar
• Shang W, Yao F, Wan P, Hu X (2008) On minimum m-connected k-dominating set problem in unit disc graphs. J. Combin. Optim. 16(2):99–106.Crossref, Google Scholar
• Shi Y, Zhang Y, Zhang Z, Wu W (2016) A greedy algorithm for the minimum 2-connected m-fold dominating set problem. J. Combin. Optim. 31(1):136–151.Crossref, Google Scholar
• Shi Y, Zhang Z, Mo Y, Du D-Z (2017) Approximation algorithm for minimum weight fault-tolerant virtual backbone in unit disk graphs. IEEE/ACM Trans. Networking 25(2):925–933.Crossref, Google Scholar
• Tang S, Yuan J, Zhang Z, Du D-Z (2017) Data set. https://www.dropbox.com/sh/5d1vcqxw1xaowk9/AADfZSBTTM6R3I3A1ACu4-l9a?dl=0.Google Scholar
• Wan P-J, Alzoubi KM, Frieder O (2002) Distributed construction of connected dominating set in wireless ad hoc networks. Proc. 21st Annual Joint Conf. IEEE Comput. Comm. Societies. Proc. IEEE, Vol. 3 (IEEE, New York), 1597–1604.Google Scholar
• Wan P-J, Wang L, Yao F (2008) Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. Distributed Comput. Systems, 2008. ICDCS’08. The 28th Internat. Conf., Beijing, 337–344.Google Scholar
• Wang F, Thai MT, Du D-Z (2009) On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans. Wireless Comm. 8(3):1230–1237.Crossref, Google Scholar
• Wang W, Liu B, Kim D, Li D, Wang J, Jiang Y (2015) A better constant approximation for minimum 3-connected m-dominating set problem in unit disk graph using Tutte decomposition. 2015 IEEE Conf. Comput. Comm. (INFOCOM), Hong Kong, 1796–1804.Google Scholar
• Wang W, Kim D, An MK, Gao W, Li X, Zhang Z, Wu W (2013) On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Trans. Networking 21(5):1499–1510.Crossref, Google Scholar
• Wu W, Du H, Jia X, Li Y, Huang SC-H (2006) Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoretical Comput. Sci. 352(1):1–7.Crossref, Google Scholar
• Wu Y, Wang F, Thai MT, Li Y (2007) Constructing k-connected m-dominating sets in wireless sensor networks. Military Comm. Conf., Orlando, FL, 1–7.Google Scholar
• Zhang Z, Gao X, Wu W, Du D-Z (2009a) A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J. Global Optim. 45(3):451–458.Crossref, Google Scholar
• Zhang Z, Liu Q, Li D (2009b) Two algorithms for connected r-hop k-dominating set. Discrete Math., Algorithms Appl. 1(4):485–498.Crossref, Google Scholar
• Zhang Z, Zhou J, Mo Y, Du D-Z (2016) Performance-guaranteed approximation algorithm for fault-tolerant connected dominating set in wireless networks. 35th Annual IEEE Internat. Conf. Comput. Comm., San Francisco, 1–8.Google Scholar
• Zhou J, Zhang Z, Wu W, Xing K (2014) A greedy algorithm for the fault-tolerant connected dominating set in a general graph. J. Combin. Optim. 28(1):310–319.Crossref, Google Scholar