Abstract
Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number α and the connected domination number γ c of a unit-disk graph plays the key role. The best-known relation between them is \(\alpha\leq3\frac{2}{3}\gamma_{c}+1\). In this paper, we prove that α≤3.4306γ c +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC02), pp. 157–164 (2002)
Bharghavan, V., Das, B.: Routing in ad hoc networks using minimum connected dominating sets. In: Proceedings of the IEEE International Conference on Communications (ICC97), pp. 376–380 (1997)
Blum, J., Ding, M., Cheng, X.: Applications of connected dominating sets in wireless networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329–369. Kluwer Academic, Dordrecht (2004)
Cadei, M., Cheng, X., Du, D.-Z.: Connected domination in ad hoc wireless networks. In: Proceedings of the 6th Joint Conference on Information Science (JCIS02), pp. 251–255 (2002)
Chvátal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Trans. Sens. Netw. 2(3), 444–453 (2006)
Li, Y.S., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wirel. Commun. Mob. Comput. 5(8), 927–932 (2005)
Lin, F., Yang, X.: Geometric Measure Theory: An Introduction. International Press, Somerville (2003)
Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13(1), 14–25 (2002)
Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mob. Netw. Appl. 9(2), 141–149 (2004)
Wan, P.-J., Wang, L., Yao, F.: Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: Proceedings of the 28th International Conference on Distributed Computing Systems, pp. 337–344 (2008)
Wu, W., Du, H., Jia, X., Li, Y., Huang, S.C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352(1–3), 1–7 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, M., Wan, PJ. & Yao, F. Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs. Algorithmica 61, 1000–1021 (2011). https://doi.org/10.1007/s00453-011-9512-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9512-7