Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Constant-time distributed dominating set approximation

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract.

Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary, possibly constant parameter k and maximum node degree \(\Delta\), our algorithm computes a dominating set of expected size \({\rm O}(k\Delta^{2/k}{\rm log}(\Delta)\vert DS_{\rm {OPT}}\vert)\) in \({\rm O}{(k^2)}\) rounds. Each node has to send \({\rm O}{(k^2\Delta)}\) messages of size \({\rm O}({\rm log}\Delta)\). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alzoubi K, Wan P-J, Frieder O: Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In: Proc. of the 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), EPFL Lausanne, Switzerland, 2002, pp 157-164

  2. Bartal Y, Byers JW, Raz D: Global Optimization Using Local Information with Applications to Flow Control. In: Proc. of the 38th IEEE Symposium on the Foundations of Computer Science (FOCS), 1997, pp 303-312

  3. Berger B, Rompel J, Shor P: Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry. J Comput Syst Sci 49:454-477 (1994)

    Google Scholar 

  4. Chvátal V: A Greedy Heuristic for the Set-Covering Problem. Math Oper Res 4(3):233-235 (1979)

    Google Scholar 

  5. Chvátal V: Linear Programming. W.H. Freeman and Company, 1983

  6. Dubhashi D, Mei A, Panconesi A, Radhakrishnan J, Srinivasan A: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp 717-724

  7. Feige U: A Threshold of \(\ln n\) for Approximating Set Cover. J. ACM (JACM) 45(4):634-652 (1998)

  8. Gao J, Guibas L, Hershberger J, Zhang L, Zhu A: Discrete Mobile Centers. In: Proc. of the 17th annual symposium on Computational geometry (SCG), ACM Press, 2001, pp 188-196

  9. Garey MR, Johnson DS: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979

  10. Guha S, Khuller S: Approximation Algorithms for Connected Dominating Sets. In: Proc. of the 4th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol 1136, 1996, pp 179-193

  11. Jia L, Rajaraman R, Suel R: An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), 2001, pp 33-42

  12. Johnson DS: Approximation Algorithms for Combinatorial Problems. J Comput Syst Sci 9:256-278 (1974)

    Google Scholar 

  13. Karp RM: Reducibility Among Combinatorial Problems. In: Proc. of a Symposium on the Complexity of Computer Computations, 1972, pp 85-103

  14. Kuhn F, Moscibroda T, Wattenhofer R: What Cannot Be Computed Locally! In: Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), 2004, pp 300-309

  15. Kutten S, Peleg D: Fast Distributed Construction of Small k-Dominating Sets and Applications. J Algorithms 28:40-66 (1998)

    Google Scholar 

  16. Lovasz L: On the Ratio of Optimal Integral and Fractional Covers. Discrete Math 13:383-390 (1975)

    Google Scholar 

  17. Luby M, Nisan N: A Parallel Approximation Algorithm for Positive Linear Programming. In: Proc. of the 25th ACM Symposium on Theory of Computing (STOC), 1993, pp 448-457

  18. Raghavan P, Thompson CD: Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs. Combinatorica 7(4):365-374 (1987)

    Google Scholar 

  19. Rajagopalan S, Vazirani V: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. SIAM J Comput 28:525-540 (1998)

    Google Scholar 

  20. Rajaraman R: Topology Control and Routing in Ad hoc Networks: A Survey. SIGACT News 33:60-73 (2002)

    Google Scholar 

  21. Slav\’ik P: A Tight Analysis of the Greedy Algorithm for Set Cover. In: Proc. of the 28th ACM Symposium on Theory of Computing (STOC), 1996, pp 435-441

  22. Wu J, Li H: On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. In: Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DialM), 1999, pp 7-14

Download references

Author information

Authors and Affiliations

  1. Computer Engineering and Networks Laboratory, ETH Zürich, 8092, Zürich, Switzerland

    Fabian Kuhn & Roger Wattenhofer

Authors
  1. Fabian Kuhn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roger Wattenhofer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fabian Kuhn.

Additional information

Received: 9 September 2003, Accepted: 2 September 2004, Published online: 13 January 2005

The work presented in this paper was supported (in part) by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kuhn, F., Wattenhofer, R. Constant-time distributed dominating set approximation. Distrib. Comput. 17, 303–310 (2005). https://doi.org/10.1007/s00446-004-0112-5

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-004-0112-5

Keywords

Search

Navigation