article

Constant-time distributed dominating set approximation

Authors:

Rogert WattenhoferAuthors Info & Claims

Distributed Computing, Volume 17, Issue 4

Pages 303 - 310

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

Published: 01 May 2005 Publication History

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 Δ, our algorithm computes a dominating set of expected size O(kΔ^2/k log (Δ)|DS_OPT|) in O (K²) rounds. Each node has to send O(k² Δ) messages of size O(log Δ). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.

References

[1]

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]

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.

Digital Library

[3]

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

Digital Library

[4]

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

Digital Library

[5]

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

[6]

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]

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

[8]

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]

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

Digital Library

[10]

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]

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]

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

Digital Library

[13]

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

[14]

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]

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

Digital Library

[16]

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

Digital Library

[17]

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]

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

Digital Library

[19]

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

Digital Library

[20]

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

Digital Library

[21]

21. Slavík 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]

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.

Cited By

Dory MGhaffari MIlchi S(2024)Near-optimal distributed dominating set in bounded arboricity graphsDistributed Computing10.1007/s00446-023-00447-z37:4(387-398)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00446-023-00447-z
Wang LZhang ZDu DMao YZhang X(2024)A Distributed Approximation Algorithm for the Total Dominating Set ProblemAlgorithmic Aspects in Information and Management10.1007/978-981-97-7798-3_11(122-132)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-981-97-7798-3_11
Dory MGhaffari MIlchi SMilani AWoelfel P(2022)Near-Optimal Distributed Dominating Set in Bounded Arboricity GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538437(292-300)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538437
Show More Cited By

Index Terms

Constant-time distributed dominating set approximation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Constant-time distributed dominating set approximation
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k and maximum ...
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For ε 1/ poly log Δ we obtain two algorithms with approximation factor (1 + ε)(1 + ł n (Δ + 1)) ...
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

We describe a simple deterministic O(ε-1 log Δ) round distributed algorithm for (2α+ 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ denotes the maximum degree. We also show a lower bound proving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 17, Issue 4

May 2005

56 pages

ISSN:0178-2770

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dory MGhaffari MIlchi S(2024)Near-optimal distributed dominating set in bounded arboricity graphsDistributed Computing10.1007/s00446-023-00447-z37:4(387-398)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00446-023-00447-z
Wang LZhang ZDu DMao YZhang X(2024)A Distributed Approximation Algorithm for the Total Dominating Set ProblemAlgorithmic Aspects in Information and Management10.1007/978-981-97-7798-3_11(122-132)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-981-97-7798-3_11
Dory MGhaffari MIlchi SMilani AWoelfel P(2022)Near-Optimal Distributed Dominating Set in Bounded Arboricity GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538437(292-300)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538437
Hernández Mira FParra Inza ESigarreta Almira JVakhania N(2022)A polynomial-time approximation to a minimum dominating set in a graphTheoretical Computer Science10.1016/j.tcs.2022.07.020930:C(142-156)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.07.020
Mo SBao ZZhang PPeng Z(2021)Towards an efficient weighted random walk dominationProceedings of the VLDB Endowment10.14778/3436905.343691514:4(560-572)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.14778/3436905.3436915
Deurer JKuhn FMaus YRobinson PEllen F(2019)Deterministic Distributed Dominating Set Approximation in the CONGEST ModelProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331626(94-103)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331626
Bacrach NCensor-Hillel KDory MEfron YLeitersdorf DPaz ARobinson PEllen F(2019)Hardness of Distributed OptimizationProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331597(238-247)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331597
Razafimandimby CLoscrí VVegni ABenslimane A(2019)Neuro-Dominating set scheme for a fast and efficient robot deployment in internet of robotic thingsAd Hoc Networks10.1016/j.adhoc.2018.08.01686:C(36-45)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.adhoc.2018.08.016
(2018)An order-based algorithm for minimum dominating set with application in graph miningInformation Sciences: an International Journal10.1016/j.ins.2017.10.033426:C(101-116)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.ins.2017.10.033
Abed SRais H(2017)Hybrid bat algorithm for minimum dominating set problemJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-1739833:4(2329-2339)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-17398
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents