DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.22

Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs

Authors: Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak, and Marcin Witkowski

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

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.

Cite as

Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak, and Marcin Witkowski. Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 22:1-22:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{czygrinow_et_al:LIPIcs.ISAAC.2018.22,
  author =	{Czygrinow, Andrzej and Hanckowiak, Michal and Wawrzyniak, Wojciech and Witkowski, Marcin},
  title =	{{Distributed Approximation Algorithms for the Minimum Dominating Set in K\underlineh-Minor-Free Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{22:1--22:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.22},
  URN =		{urn:nbn:de:0030-drops-99705},
  doi =		{10.4230/LIPIcs.ISAAC.2018.22},
  annote =	{Keywords: Distributed algorithms, minor-closed family of graphs, MDS}
}

Search Results

Documents authored by Wawrzyniak, Wojciech

Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message