Constant round distributed domination on graph classes with bounded expansion

DOI10.1007/978-3-030-79527-6_19OpenAlexW3173415711MaRDI QIDQ2117740

Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/2012.02701

zbMATH Keywords

dominating setbounded expansion graph classesLOCAL algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Related Items (2)

Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Local planar domination revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Characterisations and examples of graph classes with bounded expansion
• Hitting sets when the VC-dimension is small
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• 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
• Grad and classes with bounded expansion. I: Decompositions
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Local Computation
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Kernelization and Sparseness: the case of Dominating Set
• Distributed Dominating Set Approximations beyond Planar Graphs
• On the complexity of local distributed graph problems
• Reducibility among Combinatorial Problems
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Analytical approach to parallel repetition
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs

This page was built for publication: Constant round distributed domination on graph classes with bounded expansion