2022/03/07 by Czygrinow, Andrzej, Hanćkowiak, Michał, Witkowski, Marcin · 1 citation
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2203.03229
We prove that a simple distributed algorithm finds a constant approximation of an optimal distance-k dominating set in graphs with no K2,t-minor. The algorithm runs in a constant number of rounds. We further show how this procedure can be used to give a distributed algorithm which given ε>0 and k,t∈ ℤ+ finds in a graph G=(V,E) with no K2,t-minor a distance-k dominating set of size at most (1+ε) of the optimum. The algorithm runs in O(log^*|V|) rounds in the Local model. In particular, both algorithms work in outerplanar graphs.