Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs

DOI10.1016/J.TCS.2018.07.008zbMath1410.68381OpenAlexW2883955106MaRDI QIDQ1711828

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

Publication date: 18 January 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.07.008

zbMATH Keywords

distributed algorithmslocal algorithmsminimum dominating setbounded genus graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

Distributed domination on sparse graph classes

Cites Work

• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Survey of local algorithms
• Lower bounds for local approximation
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs
• Constant-time distributed dominating set approximation

This page was built for publication: Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs