Constant round distributed domination on graph classes with bounded expansion

DOI10.1007/978-3-030-79527-6_19MaRDI QIDQ2117740zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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 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
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Kernelization and Sparseness: the case of Dominating Set
• 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
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On the complexity of local distributed graph problems
• 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
• Tight approximation bounds for dominating set on graphs of bounded arboricity

Cited in

(2)

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

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

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