Constant-time distributed dominating set approximation

DOI10.1145/872035.872040zbMath1321.68479OpenAlexW2127622665MaRDI QIDQ5892133

Roger Wattenhofer, Fabian Kuhn

Publication date: 4 September 2015

Published in: Proceedings of the twenty-second annual symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/32917

zbMATH Keywords

linear programmingapproximation algorithmsdistributed algorithmsdominating setsad-hoc networks

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (12)

Distributed algorithms for weighted problems in sparse graphs ⋮ Distributed algorithms for random graphs ⋮ A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Graph polynomials ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Leveraging Linial’s Locality Limit ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Approximation algorithms for channel allocation problems in broadcast networks ⋮ Distributed Spanner Approximation

Cites Work

• Unnamed Item

This page was built for publication: Constant-time distributed dominating set approximation