Distributed Dominating Set Approximations beyond Planar Graphs

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

zbMATH Keywords

dominating setdistributed computingapproximation algorithms

Mathematics Subject Classification ID

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