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)

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