A New Approximation Algorithm for Minimum-Weight $(1,m)$–Connected Dominating Set

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. Broy M, Denert E, eds. APPROX’06/RANDOM’06, Lecture Notes in Computer Science, vol. 4110, no. 1 (Springer-Verlag, Barcelona, Spain), 3–14.Crossref, Google Scholar
• Cheng X, Huang X, Li D, Wu W, Du D-Z (2010) A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 43(4):202–208.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.Google Scholar
• Das B, Bharghavan V (1997) Routing in ad-hoc networks using minimum connected dominating sets. Proc. ICC’97 Internat. Conf. Commun., vol. 1 (IEEE, Piscataway, NJ), 376–380.Google Scholar
• Du D-Z, Wan P-J (2012) Connected Dominating Set: Theory and Applications, Springer Optimization and Its Applications, vol. 77 (Springer, New York).Google Scholar
• Du D-Z, Ker-I Ko, Xiaodong Hu (2012) Design and Analysis of Approximation Algorithms, Springer Optimization and Its Applications, vol. 62 (Springer, New York).Crossref, 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. Shang-Hua Teng, ed. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, 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.Google Scholar
• Erlebach T, Mihalák M (2009) A (4+ε)-approximation for the minimum-weight dominating set problem in unit disk graphs. Proc. 7th Internat. Conf. Approximation Online Algorithms (Springer-Verlag, Berlin), 135–146.Google Scholar
• Feige U (1996) Threshold of ln n for approximating set cover. Proc. 28th Annual ACM Sympos. Theory Comput. (ACM, New York), 314–318.Google Scholar
• Fukunaga T (2018) Approximation algorithms for highly connected multi-dominating sets in unit disk graphs. Algorithmica 80(11):3270–3292.Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, vol. 174 (Freeman, San Francisco).Google Scholar
• Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20: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.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.Google Scholar
• Li J, Jin Y (2015) A PTAS for the weighted unit disk cover problem. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Proc. 42nd Internat. Colloquium Automata Languages Programming (Springer, Berlin), 898–909.Google Scholar
• Liao Q, Li Z (2014) Portfolio optimization of computer and mobile botnets. Internat. J. Inform. Security 13:1–14.Crossref, Google Scholar
• Nutov Z (2022) Approximating k-connected m-dominating set problems. Algorithmica 84:1511–1525.Google Scholar
• Ruan L, Du H, Jia X, Wu W, Li Y, Ko K (2004) A greedy approximation for minimum connected dominating sets. Theoretical Comput. Sci. 329(1–3):325–330.Google Scholar
• Salhieh A, Weinmann J, Kochhal M, Schwiebert L (2001) Power efficient topologies for wireless sensor networks. Internat. Conf. Parallel Processing (IEEE, Piscataway, NJ), 156–163.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.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. Networks 25(2):925–933.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.Google Scholar
• Wan P-J, Alzoubi KM, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks Appl. 9(2):141–149.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. Networks 21(5):1499–1510.Google Scholar
• Wu W, Zhang Z, Lee W, Du D-Z (2020) Optimal Coverage in Wireless Sensor Networks, Springer Optimization and Its Applications, vol. 162 (Springer, New York).Google Scholar
• Zhang Z (2016) Survey of approximation algorithm on virtual backbone of wireless sensor network (Chinese). J. Comput. Res. Development 53(1):15–25.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.Google Scholar
• Zhang Z, Zhou J, Tang S, Huang X, Du D-Z (2018) Computing minimum k connected m-fold dominating set in general graphs. INFORMS J. Comput. 30(2):217–224.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.Google Scholar
• Zhou J, Zhang Z, Tang S, Huang X, Du D-Z (2018) Breaking the o(lnn) barrier: An enhanced approximation algorithm for fault-tolerant minimum weight connected dominating set. INFORMS J. Comput. 30(2):225–235.Google Scholar
• Zhou J, Zhang Z, Ran Y, Pardalos PM, Tang ST, Du D (2024) A new approximation algorithm for minimum-weight (1,m)–connected dominating set. https://doi.org/10.1287/ijoc.2023.0306.cd, https://github.com/INFORMSJoC/2023.0306.Google Scholar
• Zhou J, Zhang Z, Tang S, Huang X, Mo Y, Du D-Z (2017) Fault-tolerant virtual backbone in heterogeneous wireless sensor network. IEEE/ACM Trans. Networks 25(6):3487–3499.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 minimumweighted connected dominating sets on unit disk graphs. Theoretical Comput. Sci. 412(3):198–208.Google Scholar