Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
DOI10.1016/j.tcs.2016.12.001zbMath1356.05146OpenAlexW2561474155MaRDI QIDQ501664
Edyta Szymańska, Marcin Witkowski, Michał Hanćkowiak, Andrzej Czygrinow, Wojciech Wawrzyniak
Publication date: 9 January 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.12.001
Planar graphs; geometric and topological aspects of graph theory (05C10) 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 (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed minimum dominating set approximations in restricted families of graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Algorithmic aspects of the \(k\)-domination problem in graphs
- Survey of local algorithms
- The Algorithmic Complexity of k-Domatic Partition of Graphs
- Lower bounds for local approximation
- Fast Distributed Approximations in Planar Graphs
- Distributed Computing: A Locality-Sensitive Approach
- An efficient distributed algorithm for constructing small dominating sets
This page was built for publication: Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs