Constant round distributed domination on graph classes with bounded expansion

2020/12/04 by Kublenz, Simeon, Siebertz, Sebastian, Vigny, Alexandre
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2012.02701

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.

Related

• Distributed domination on sparse graph classes
• Distributed Domination on Graph Classes of Bounded Expansion
• Local planar domination revisited
• Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
• Distributed distance domination in graphs with no K_2,t-minor