Constant-time distributed dominating set approximation

By F. Kuhn, Roger Wattenhofer. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2003

401 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Does topology control reduce interference? (2004, background): “Most of these proposals are based on (connected) dominating sets [1, 2, 9] and focus on locality and provable properties, such as [12], which achieves a non-trivial approximation of the minimum dominating set in constant time.”
Distributed verification and hardness of distributed approximation (2010, background): “[5] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer.”
A Survey of Caching Mechanisms in Information-Centric Networking (2015, neutral): “, through greedy algorithms [42], [43]).”
Distributed clustering in ad-hoc sensor networks: a hybrid, energy-efficient approach (2004, methodology): “The approach in [23] selects a d-hop dominating set inO(d) time to cluster the network based on node ID, while the approach in [32] selects a dominating set i n constant time using linear programming relaxation techniq ues.”
Ad hoc networks beyond unit disk graphs (2003, background): “Many of them are based on dominating sets [1, 10, 11, 13, 14, 19, 29] or angle of arrival [30].”