Constant-time distributed dominating set approximation
- 13 July 2003
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 17 (4) , 25-32
- https://doi.org/10.1145/872035.872040
Abstract
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 degree Δ, our algorithm computes a dominating set of expected size O(kΔ2/k log Δ|DSOPT|) in O(k2) rounds where each node has to send O(k2Δ) messages of size O(logΔ). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.Keywords
This publication has 13 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Message-optimal connected dominating sets in mobile ad hoc networksPublished by Association for Computing Machinery (ACM) ,2002
- Topology control and routing in ad hoc networksACM SIGACT News, 2002
- On calculating connected dominating set for efficient routing in ad hoc wireless networksPublished by Association for Computing Machinery (ACM) ,1999
- Fast Distributed Construction of Smallk-Dominating Sets and ApplicationsJournal of Algorithms, 1998
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer ProgramsSIAM Journal on Computing, 1998
- Efficient NC algorithms for set cover with applications to learning and geometryJournal of Computer and System Sciences, 1994
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972