Back to Search Start Over

Constant round distributed domination on graph classes with bounded expansion

Authors :
Kublenz, Simeon
Siebertz, Sebastian
Vigny, Alexandre
Publication Year :
2020

Abstract

We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graphs with excluded topological minors.<br />Paper accepted at SIROCCO 2021, implemented reviews, corrected an error in Lemma 1

Subjects

Subjects :
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Computer Science - Distributed, Parallel, and Cluster Computing
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
Distributed, Parallel, and Cluster Computing (cs.DC)
Computer Science - Discrete Mathematics

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....779b835d3985b8c3eae8bbc13db2a45b

Tools

Authors Abstract Subjects Details