Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs

DOI10.1016/J.TCS.2016.12.001zbMATH Open1356.05146OpenAlexW2561474155MaRDI QIDQ501664FDOQ501664

Edyta Szymańska, Marcin Witkowski, Michal Hanckowiak, 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

zbMATH Keywords

distributed graph algorithms

Mathematics Subject Classification ID

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• Fast Distributed Approximations in Planar Graphs
• Distributed minimum dominating set approximations in restricted families of graphs
• 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
• Lower bounds for local approximation
• An efficient distributed algorithm for constructing small dominating sets

Cited In (6)

• Local certification of graphs with bounded genus
• Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
• Compact distributed certification of planar graphs
• Distributed distance-\(r\) covering problems on sparse high-girth 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)