Distributed Dominating Set Approximations beyond Planar Graphs
From MaRDI portal
Abstract: The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, there has been much progress on computing local approximations on sparse graphs, and in particular planar graphs. In this paper we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bounds for planar graphs can be lifted to bounded genus graphs, and present (1) a local constant-time, constant-factor MDS approximation algorithm and (2) a local -time approximation scheme. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments.
Recommendations
- Distributed Approximation Algorithms for Planar Graphs
- Distributed approximation of capacitated dominating sets
- Constant-time distributed dominating set approximation
- Constant-time distributed dominating set approximation
- Distributed minimum dominating set approximations in restricted families of graphs
- A distributed algorithm for k-dominating sets
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Distributed algorithms for \textsc{Edge Dominating Sets}
- Deterministic distributed dominating set approximation in the CONGEST model
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- A local constant factor MDS approximation for bounded genus graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Almost optimal set covers in finite VC-dimension
- Analytical approach to parallel repetition
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for combinatorial problems
- Diameter and treewidth in minor-closed graph families
- Distributed minimum dominating set approximations in restricted families of graphs
- Fast Distributed Approximations in Planar Graphs
- Graphs on surfaces
- Greedy domination on biclique-free graphs
- Hitting sets when the VC-dimension is small
- Leveraging Linial’s Locality Limit
- Local computation: lower and upper bounds
- Local tree-width, excluded minors, and approximation algorithms
- Locality in Distributed Graph Algorithms
- Minimum dominating set approximation in graphs of bounded arboricity
- On the ratio of optimal integral and fractional covers
- Reducibility among combinatorial problems
- Sparsity. Graphs, structures, and algorithms
- Stone age distributed computing
- Survey of local algorithms
- Tight approximation bounds for dominating set on graphs of bounded arboricity
Cited in
(22)- Local certification of graphs with bounded genus
- Minimum dominating set approximation in graphs of bounded arboricity
- Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Near-optimal distributed DFS in planar graphs
- Fast Distributed Approximations in Planar Graphs
- Compact distributed certification of planar graphs
- Distributed domination on sparse graph classes
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Distributed minimum dominating set approximations in restricted families of graphs
- Distributed Approximation Algorithms for Planar Graphs
- Near-optimal distributed dominating set in bounded arboricity graphs
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- Distributed approximation of capacitated dominating sets
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Local planar domination revisited
- Constant round distributed domination on graph classes with bounded expansion
- A local constant factor MDS approximation for bounded genus graphs
This page was built for publication: Distributed Dominating Set Approximations beyond Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972685)
