Distributed Dominating Set Approximations beyond Planar Graphs
From MaRDI portal
Publication:4972685
DOI10.1145/3326170zbMath1454.68090arXiv1705.09617OpenAlexW2963948964WikidataQ127660542 ScholiaQ127660542MaRDI QIDQ4972685
Saeed Akhoondian Amiri, Sebastian Siebertz, Stefan Schmid
Publication date: 25 November 2019
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.09617
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (6)
The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Distributed minimum dominating set approximations in restricted families of graphs
- Sparsity. Graphs, structures, and algorithms
- Hitting sets when the VC-dimension is small
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Diameter and treewidth in minor-closed graph families
- Tight approximation bounds for dominating set on graphs of bounded arboricity
- Greedy domination on biclique-free graphs
- Almost optimal set covers in finite VC-dimension
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Local tree-width, excluded minors, and approximation algorithms
- Survey of local algorithms
- Local Computation
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- Locality in Distributed Graph Algorithms
- Approximation algorithms for NP-complete problems on planar graphs
- Reducibility among Combinatorial Problems
- Stone age distributed computing
- Analytical approach to parallel repetition
- A Local Constant Factor MDS Approximation for Bounded Genus Graphs
This page was built for publication: Distributed Dominating Set Approximations beyond Planar Graphs