Help
Cart
Skip main navigation

Available Issues

April 12, 2013 - April 13, 2026

Available Issues

April 12, 2013 - April 13, 2026

Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set

Published Online:26 Mar 2018https://doi.org/10.1287/ijoc.2017.0775

References

  • Ambühl C, Erlebach T, Mihalák M, Nunkesser M (2006) Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. Díaz J, Jansen K, Rolim JDP, Zwick U, eds. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, LNCS, Vol. 4110 (Springer, Berlin), 3–14.Crossref, Google Scholar
  • 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
  • Buchanan A, Sung JS, Butenko S, Pasiliao EL (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J. Comput. 27(1):178–188.Link, Google Scholar
  • Byrka J, Grandoni F, Rothvoß T, Sanità L (2010) An improved LP-based approximation for Steiner tree. Proc. 42nd ACM Sympos. Theory Comput., Cambridge, MA, 583–592.Google Scholar
  • Byrka J, Grandoni F, Rothvoß T, Sanità L (2013) Steiner tree approximation via iterative randomized rounding. J. ACM (JACM) 60(1):Article no. 6.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, Wu J (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. Comm., 1997. ICC’97 Montreal, Towards the Knowledge Millennium. 1997 IEEE Internat. Conf., Montreal, 376–380.Google Scholar
  • Du D-Z, Wan P-J (2012) Connected Dominating Set: Theory and Applications, Vol. 77 (Springer Science & Business Media, New York).Google Scholar
  • Du D-Z, Ko K-I, Hu X (2011) Design and Analysis of Approximation Algorithms, Vol. 62 (Springer Science & Business Media, New York).Google Scholar
  • Du D-Z, Graham RL, Pardalos PM, Wan P-J, Wu W, Zhao W (2008) Analysis of greedy approximations with nonsubmodular potential functions. Proc. Nineteenth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 167–175.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
  • Erlebach T, Mihalák M (2009) A (4 + ɛ)-approximation for the minimum-weight dominating set problem in unit disk graphs. Bampis E, Jansen K, eds. Approximation and Online Algorithms (Springer, Berlin), 135–146.Google Scholar
  • Erlebach T, Grant T, Kammer F (2011) Maximising lifetime for fault-tolerant target coverage in sensor networks. Sustainable Comput.: Informatics Systems 1(3):213–225.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 preprint, arXiv:1511.09156.Google Scholar
  • Galbiati G, Maffioli F, Morzenti A (1994) A short note on the approximability of the maximum leaves spanning tree problem. Inform. Processing Lett. 52(1):45–49.Crossref, Google Scholar
  • Gendron B, Lucena A, da Cunha AS, Simonetti L (2014) Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS J. Comput. 26(4):645–657.Link, Google Scholar
  • Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387.Crossref, Google Scholar
  • Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inform. Comput. 150(1):57–74.Crossref, Google Scholar
  • Huang Y, Gao X, Zhang Z, Wu W (2009) A better constant-factor approximation for weighted dominating set in unit disk graph. J. Combinatorial Optim. 18(2):179–194.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 J, Jin Y (2015) A PTAS for the weighted unit disk cover problem. Halldórsson M, Iwama K, Kobayashi N, Speckmann B, eds. Automata, Languages, and Programming (LNCS) (Springer, Berlin), 898–909.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
  • Nutov Z (2012) Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Trans. Algorithms 9(1):417–426.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. Theoret. Comput. Sci. 329(1):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. Combinatorial 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. Combinatorial 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 graph. IEEE/ACM Trans. Networking 25(2):925–933.Crossref, Google Scholar
  • Solis-Oba R (1998) 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves (Springer, New York).Crossref, Google Scholar
  • Wan P-J, Alzoubi KM, Friede O (2002) Distributed construction of connected dominating set in wireless ad hoc networks. INFOCOM 2002. Twenty-First Annual Joint Conf. IEEE Comput. Comm. Societies. Proc. IEEE, Vol. 3 (IEEE, New York), 1597–1604.Google Scholar
  • Wang F, Thai MT, Du D-Z (2009) On the construction of 2-connected virtual backbone in wireless networks. Wireless Comm., IEEE Trans. 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. Comput. Comm. (INFOCOM), 2015 IEEE Conf., 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. Networking, IEEE/ACM Trans. 21(5):1499–1510.Crossref, Google Scholar
  • Willson J, Zhang Z, Wu W, Du D-Z (2015) Fault-tolerant coverage with maximum lifetime in wireless sensor networks. Comput. Comm. (INFOCOM), 2015 IEEE Conf., Hong Kong, 1364–1372.Google Scholar
  • Zhang Z, Shi Y (2015) Approximation algorithm for minimum weight fault-tolerant virtual backbone in homogeneous wireless sensor network. Comput. Comm. (INFOCOM), 2015 IEEE Conf., Hong Kong, 1080–1085.Google Scholar
  • Zhang Z, Gao X, Wu W, Du D-Z (2009) 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, Zhou J, Mo Y, Du D-Z (2016b) 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
  • Zhang Z, Zhou J, Tang S, Huang X, Du D (2017) Computing minimum k-connected m-fold dominating set in general graphs. INFORMS J. Comput. Forthcoming.Google Scholar
  • Zhang Z, Willson J, Lu Z, Wu W, Zhu X, Du D (2016a) Approximating maximum lifetime k-coverage through minimizing weighted k-cover in homogeneous wireless sensor networks. IEEE/ACM Trans. Networking 24(6):3620–3633.Crossref, 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. Combinatorial Optim. 28(1):310–319.Crossref, Google Scholar
  • Zou F, Li X, Gao S, Wu W (2009) Node-weighted Steiner tree approximation in unit disk graphs. J. Combinatorial Optim. 18(4):342–349.Crossref, Google Scholar
  • Zou F, Wang Y, Xu X-H, Li X, Du H, Wan P, Wu W (2011) New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoret. Comput. Sci. 412(3):198–208.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree