Constant round distributed domination on graph classes with bounded expansion

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

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

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

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)