Constant-time distributed dominating set approximation
From MaRDI portal
Publication:5892133
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
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
This page was built for publication: Constant-time distributed dominating set approximation
