Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs

DOI10.4230/LIPIcs.ISAAC.2018.22OpenAlexW2906807966MaRDI QIDQ5091012

Marcin Witkowski, Wojciech Wawrzyniak, Michał Hanćkowiak, Andrzej Czygrinow

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.isaac.2018.22

zbMATH Keywords

distributed algorithmsMDSminor-closed family of graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

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

Cites Work

• Distributed minimum dominating set approximations in restricted families of graphs
• Fast Distributed Approximations in Planar Graphs
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs

This page was built for publication: Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs