Distributed domination on sparse graph classes

DOI10.1016/J.EJC.2023.103773MaRDI QIDQ6614403zbMATH OpenFDO

Authors Ozan Heydt, Simeon Kublenz, P. Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny

Publication date 7 October 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103773

zbMATH Keywords

dominating set problem

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Distributed Dominating Set Approximations beyond Planar Graphs
• Minimum dominating set approximation in graphs of bounded arboricity
• Constant-factor approximation of the domination number in sparse graphs
• Distributed Approximation Algorithms for Planar Graphs
• A local constant factor MDS approximation for bounded genus graphs

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• 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 combinatorial problems
• Approximation algorithms for polynomial-expansion and low-density graphs
• Characterisations and examples of graph classes with bounded expansion
• Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed minimum dominating set approximations in restricted families of graphs
• Fast Distributed Approximations in Planar Graphs
• Grad and classes with bounded expansion. I: Decompositions
• Greedy domination on biclique-free graphs
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7774264 (Why is no real title available?)
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization using structural parameters on sparse graph classes
• Leveraging Linial’s Locality Limit
• Local computation: lower and upper bounds
• Lossy kernels for connected dominating set on sparse graphs
• Minimum dominating set approximation in graphs of bounded arboricity
• Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs
• On the complexity of local distributed graph problems
• On the degrees of the vertices of a directed graph
• On the ratio of optimal integral and fractional covers
• Parameterized complexity of directed Steiner tree on sparse graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Progressive algorithms for domination and independence
• Reducibility among combinatorial problems
• Sparsity. Graphs, structures, and algorithms
• Survey of local algorithms
• Tight approximation bounds for dominating set on graphs of bounded arboricity

Cited in

(3)

• Distributed distance domination in graphs with no \(K_{2,t}\)-minor
• Distributed distance-r covering problems on sparse high-girth graphs
• Autonomous domination

This page was built for publication: Distributed domination on sparse graph classes

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