A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

DOI10.1016/J.IPL.2013.11.008MaRDI QIDQ2445394zbMATH OpenOpenAlexFDO

Authors Wojciech Wawrzyniak

Publication date 14 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.11.008

zbMATH Keywords

approximation algorithmsdistributed algorithmdominating setlocal algorithmplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Distributed Dominating Set Approximations beyond Planar Graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Distributed Approximation Algorithms for Planar Graphs
• A local constant factor MDS approximation for bounded genus graphs

Cites work

• Distributed Computing: A Locality-Sensitive Approach
• Distributed minimum dominating set approximations in restricted families of graphs
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• Survey of local algorithms

Cited in

(21)

• Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
• Compact distributed certification of planar graphs
• Local planar domination revisited
• Local certification of graphs with bounded genus
• Constant round distributed domination on graph classes with bounded expansion
• Distributed distance domination in graphs with no \(K_{2,t}\)-minor
• Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Distributed Dominating Set Approximations beyond Planar Graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• A local constant factor MDS approximation for bounded genus graphs
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Distributed domination on sparse graph classes
• Near-optimal distributed dominating set in bounded arboricity graphs
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Quantum alternating operator ansatz for solving the minimum dominating set problem on sparse graphs with a specific structure
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Efficient distributed decomposition and routing algorithms in minor-free networks and their applications
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks

This page was built for publication: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445394)