Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
DOI10.1016/J.TCS.2016.12.001zbMATH Open1356.05146OpenAlexW2561474155MaRDI QIDQ501664FDOQ501664
Authors: Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymańska, Wojciech Wawrzyniak, Marcin Witkowski 
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
Recommendations
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Distributed Dominating Set Approximations beyond Planar Graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Distributed Approximation Algorithms for Planar Graphs
- A local constant factor MDS approximation for bounded genus graphs
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distributed algorithms (68W15)
Cites Work
- Graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Fast Distributed Approximations in Planar Graphs
- Distributed minimum dominating set approximations in restricted families of graphs
- Title not available (Why is that?)
- Algorithmic aspects of the \(k\)-domination problem in graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Survey of local algorithms
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- The algorithmic complexity of \(k\)-domatic partition of graphs
- An efficient distributed algorithm for constructing small dominating sets
Cited In (10)
- Local certification of graphs with bounded genus
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Compact distributed certification of planar graphs
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- A local constant factor MDS approximation for bounded genus graphs
- Local planar domination revisited
- Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501664)
