Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes | SpringerLink
Skip to main content
Springer Nature Link
Log in

Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

Many protocols in ad-hoc networks use dominating and connected dominating sets, for example for broadcasting and routing. For large ad hoc networks the construction of such sets should be local in the sense that each node of the network should make decisions based only on the information obtained from nodes located a constant number of hops from it. In this paper we use the location awareness of the network, i.e. the knowledge of position of nodes in the plane to provide local, constant approximation, deterministic algorithms for the construction of dominating and connected dominating sets of a Unit Disk Graph (UDG). The size of the constructed set, in the case of the dominating set, is shown to be 5 times the optimal, while for the connected dominating set 7.453 + ε the optimal, for any arbitrarily small ε> 0. These are to our knowledge the first local algorithms whose time complexities and approximation bounds are independent of the size of the network.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected-dominating-set construction for routing in mobile ad hoc networks. In: MOBIHOC 2002, pp. 157–164 (2002)

    Google Scholar 

  2. Aspnes, J., Bush, C., Dolev, S., Fatouroum, P., Georgiou, C., Shvartsman, A., Spirakis, P., Wattenhofer, R.: Eight open problems in distributed computing. Bulletin of the European Association for Theoretical Computer Science 90(109) (October 2006) Columns: Distributed Computing.

    Google Scholar 

  3. Awerbuch, B., Peleg, D.: Sparse partitions (extended abstract). In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 503–513 (1990)

    Google Scholar 

  4. Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Computational Geometry: Theory and Applications 9, 3–24 (1998)

    MATH  MathSciNet  Google Scholar 

  5. Chávez, E., Dobrev, S., Kranakis, E., Opatrny, J., Stacho, L., Urrutia, J.: Local construction of planar spanners in unit disk graphs with irregular transmission ranges. In: Correa, J.R., Hevia, A., Kiwi, M.A. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 286–297. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Cheng, X., Huang, X., Li, D., Du, D.-Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86, 165–177 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  8. Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. Journal of Discrete Algorithms 5, 187–201 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distributed Computing 16, 121–163 (2003)

    Article  Google Scholar 

  10. Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum cds in unit disk graphs. ACM Transactions on Sensor Networks 2(3), 444–453 (2006)

    Article  Google Scholar 

  11. 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)

    Article  MATH  MathSciNet  Google Scholar 

  12. Irving, R.W.: On approximating the minimum independent dominating set. Information Processing Letters 37, 197–200 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  13. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Discrete Mobile Centers. Discrete & Computational Geometry 30(1), 45–63 (2001)

    MathSciNet  Google Scholar 

  14. Jia, L., Rajaraman, R., Suel, R.: An efficient distributed algorithm for constructing small dominating sets. Distributed Computing 14, 193–205 (2002)

    Article  Google Scholar 

  15. Johnson, D.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256–278 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distributed Computing 17(4), 303–310 (2005)

    Article  Google Scholar 

  17. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 300–309 (2004)

    Google Scholar 

  18. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit disk graph approximation. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications; later DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pp. 17–23 (2004)

    Google Scholar 

  19. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications; later DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pp. 97–103 (2005)

    Google Scholar 

  20. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: 24th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 60–68 (2005)

    Google Scholar 

  21. Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: SODA, pp. 980–989. ACM Press, New York (2006)

    Chapter  Google Scholar 

  22. Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  23. Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proc. 17th Annual ACM Symposium on Theory of Computing (STOCS), May 1985, pp. 1–10 (1985)

    Google Scholar 

  24. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM 41, 960–981 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  25. Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Geometry based heuristics for unit disk graphs. ArXiv Mathematics e-prints (1994)

    Google Scholar 

  26. Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. on Computing 24, 1259–1277 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  27. Nieberg, T., Hurink, J.: A PTAS for the minimum dominating set problem in unit disk graphs. In: Approximation and Online Algorithms, pp. 296–306 (2006)

    Google Scholar 

  28. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)

    Google Scholar 

  29. Wang, Y., Li, X.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: Proc. of the 2003 joint workshop on Foundations of mobile computing (DIALM-POMC 2003), pp. 59–68. ACM Press, New York (2003)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Départ. d’informatique, Univ. du Québec en Outaouais, Gatineau, QC, Canada

    J. Czyzowicz

  2. Slovak Academy of Sciences, Bratislava, Slovakia

    S. Dobrev

  3. Department of CSE, Concordia University, Montréal, QC, Canada

    T. Fevens & J. Opatrny

  4. Centro de Investigacion en Matematicas, Guanajuato, Gto., Mexico

    H. González-Aguilar

  5. School of Computer Science, Carleton University, Ottawa, ON, Canada

    E. Kranakis

  6. Instituto de Matemáticas, Área de la investigación cientifica, D.F. México, México

    J. Urrutia

Authors
  1. J. Czyzowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Dobrev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. T. Fevens
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. H. González-Aguilar
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. E. Kranakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. J. Opatrny
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. J. Urrutia
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Czyzowicz, J. et al. (2008). Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes . In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation