Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
Andrzej Czygrinow, Michał Hańćkowiak, Wojciech Wawrzyniak, Marcin Witkowski · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
In this paper we will give two distributed approximation algorithms (in the Local model) for the minimum dominating set problem. First we will give a distributed algorithm which finds a dominating set D of size O(gamma(G)) in a graph G which has no topological copy of K_h. The algorithm runs L_h rounds where L_h is a constant which depends on h only. This procedure can be used to obtain a distributed algorithm which given epsilon>0 finds in a graph G with no K_h-minor a dominating set D of size at most (1+epsilon)gamma(G). The second algorithm runs in O(log^*{|V(G)|}) rounds.