2026-07-21T19:38:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9970 2024-03-06T10:45:14Z ddc:004 open_access

Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs Czygrinow, Andrzej Hanckowiak, Michal Wawrzyniak, Wojciech Witkowski, Marcin Distributed algorithms minor-closed family of graphs MDS 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrzej Czygrinow and Michal Hanckowiak and Wojciech Wawrzyniak and Marcin Witkowski 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.22 urn:nbn:de:0030-drops-99705 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode