Abstract
Connected Dominating Set is widely used as virtual backbone in wireless Ad-hoc and sensor networks to improve the performance of transmission and routing protocols. Based on special characteristics of Ad-hoc and sensor networks, we usually use unit disk graph to represent the corresponding geometrical structures, where each node has a unit transmission range and two nodes are said to be adjacent if the distance between them is less than 1. Since every Maximal Independent Set (MIS) is a dominating set and it is easy to construct, we can firstly find a MIS and then connect it into a Connected Dominating Set (CDS). Therefore, the ratio to compare the size of a MIS with a minimum CDS becomes a theoretical upper bound for approximation algorithms to compute CDS. In our paper, with the help of Voronoi diagram and Euler’s formula, we improved this upper bound, so that improved the approximations based on this relation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B.S.: Approximation algorithms for NP-complete Problems on Planar Graphs. Journal of the ACM 41(1), 153–180 (1994)
Blum, J., Ding, M., Thaeler, A., Cheng, X.Z.: Connected Dominating Set in Sensor Networks and MANETs. Handbook of Combinatorial Optimization, 329–369 (2004)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discrete Mathematics 86, 165–177 (1990)
Funke, S., Kesselman, A., Meyer, U.: A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs. ACM Transactions on Sensor Networks 2(3), 444–453 (2006)
Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. Journal of the ACM 32(1), 130–136 (1985)
Huang, G.T.: Casting the Wireless Sensor Net. Technology Review, 50–56 (2003)
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-hard Problems for Geometric Graphs. Journal of Algorithms 26(2), 238–274 (1998)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59–68 (1995)
Min, M., Du, H.W., Jia, X.H., Huang, C.X., Huang, S.C., Wu, W.L.: Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks. Journal of Global Optimization 35, 111–119 (2006)
Salem, H., Mohamed, N.: Middleware Challenges and Approaches for Wireless Sensor Networks. IEEE Distributed Systems Online 7(3) (2006); art. no. 0603-o3001
Voronoi, G.M.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième Mémoire: Recherches sur les parallélloèdres primitifs. J. Reine Angew. Math. 134, 198–287 (1908)
Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. In: Proceedings of the Third ACM Internat. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7–14 (1999)
Wu, W.L., Du, H.W., Jia, X.H., Li, Y.S., Huang, S.C.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theorital Computer Science 352, 1–7 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, X., Gao, X., Wu, W. (2008). A Better Theoretical Bound to Approximate Connected Dominating Set in Unit Disk Graph. In: Li, Y., Huynh, D.T., Das, S.K., Du, DZ. (eds) Wireless Algorithms, Systems, and Applications. WASA 2008. Lecture Notes in Computer Science, vol 5258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88582-5_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-88582-5_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88581-8
Online ISBN: 978-3-540-88582-5
eBook Packages: Computer ScienceComputer Science (R0)