Abstract
Given a connected graph \(G=(V,E)\). A subset \(C\subseteq V\) is a dominating set if every vertex of V is either in C or adjacent to a vertex in C. Further, C is a connected dominating set if C is a dominating set and the induced subgraph G[C] is connected. The Minimum Connected Dominating Set (Min-CDS) problem asks to find a connected dominating set with the minimum size, which finds applications in communication networks, in particular, as a virtual backbone in wireless sensor networks. This paper focuses on a variant of the classic Min-CDS problem, called Minimum Connected Dominating Set with Labeling (Min-CDSL), in which we are given a connected graph with vertex labels, and are required to find a connected dominating set C such that the number of labels in C (instead of |C|) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly \(\mathcal {NP}\)-\(\mathrm {complete}\). We give an approximation algorithm for Min-CDSL within performance ratio bounded by \(\ln |V(G)|+\mathrm {span}(G)+1\), where \(\mathrm {span}(G)\) refers to the maximum span of the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, \(\mathrm {span}(G)\ll |V(G)|\) and for a series of labeled graphs \(\mathrm {span}(G)=O(1)\). For a random graph \(G\in {G_{n,p}}\), \(\mathrm {span}(G)=O(\ln |V(G)|)\) almost surely, and thus our approximation ratio is \(O(\ln |V(G)|)\) which is reasonable comparing with the best known approximation ratio \(\ln |V(G)|+1\) for Min-CDS.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A simple graph is a graph without loops and parallel edges.
References
Du, D., Wan, P.: Connected Dominating Set: Theory and Applications. Springer Optimization and Its Applications, vol. 77. Springer, New York (2013)
Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 908–920 (2004)
Eriksson, H.: MBone: the multicast backbone. Commun. ACM 37(8), 54–60 (1994)
Sampathkumar, E., Walikar, H.B.: The connected domination number of a graph. J. Math. Phys. Sci. 13(6), 607–613 (1979)
Wang, F., Thai, M.T., Du, D.-Z.: On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans. Wirel. Commun. 8(3), 1230–1237 (2009)
Wu, J., Dai, F.: Virtual backbone construction in MANETs using adjustable transmission ranges. IEEE Trans. Mob. Comput. 5(9), 1188–1200 (2006)
Stefanakos, S.: Reliable Routings in Networks with Generalized Link Failure Events. International Federation for Information Processing, pp. 221–232. Springer, Berlin (2006)
Chaudhuri, S., Hjálmtýsson, G., Yates, J.: Control of lightpaths in an optical network. IETF Internet Draft (2000)
Chiu, A.L., Strand, J., Tkach, R.: Issues for routing in the optical layer. IEEE Commun. Mag. 39(2), 81–87 (2001)
Papadimitriou, D., Poppe, F., Jones, J., Venkatachalam, S., Dharanikota, S., Jain, R., Hartani, R., Griffith, D.: Inference of shared risk link groups. IETF Draft, OIF Contribution, OIF 2001-066
Sebos, P., Yates, J., Hjlmtsson, G., Greenberg, A.: Auto-discovery of shared risk link groups. In: Proceedings of IEEE/OSA OFC, vol. 3, pp. WDD3-1–WDD3-3 (2001)
Coudert, D., Datta, P., Perennes, S., Rivano, H., Voge, M.-E.: Shared risk resource group: complexity and approximability issues. Parallel Process. Lett. 17(2), 169–184 (2007)
Faragó, A.: A graph theoretic model for complex network failure scenarios. In: Proceedings of the Eighth INFORMS Telecommunications Conference, Dallas (2006)
Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. Proc. IEEE InfoCom 4, 2658–2669 (2005)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)
Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.: A greedy approximation for minimum connected dominating sets. Theoret. Comput. Sci. 329, 325–330 (2004)
Du, D.Z., Graham, R.L, Pardalos, P.M., Wan, P.J., Wu, W., Zhao, W.: Analysis of greedy approximation with nonsubmodular potential functions. In: Proceedings, 19th ACM-SIAM Symposiumon Discrete Algorithms, pp. 167–175 (2008)
Chang, R., Leu, S.: The minimum labeling spanning trees. Inf. Process. Lett. 63, 277–282 (1997)
Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Gr. Theory 17, 259–269 (1997)
Krumke, S., Wirth, H.: On the minimum label spanning tree problem. Inf. Process. Lett. 66, 81–85 (1998)
Wan, Y., Chen, G., Xu, Y.: A note on the minimum label spanning tree. Inf. Process. Lett. 84, 99–101 (2002)
Xiong, Y., Golden, B., Wasil, E.: Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem. Oper. Res. Lett. 33, 77–80 (2005)
Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)
Du, D., Ko, K., Hu, X.: Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications, vol. 62. Springer, New York (2012)
Grimmett, G.R., McDiarmid, C.J.H.: On coloring random graphs. Math. Proc. Camb. Philos. Soc. 77, 313–324 (1975)
Acknowledgements
This work is supported by the National Natural Science Foundation of China (No. 11971376).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Yang, Z., Shi, M. & Wang, W. Greedy approximation for the minimum connected dominating set with labeling. Optim Lett 15, 685–700 (2021). https://doi.org/10.1007/s11590-020-01628-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-020-01628-6