LIPIcs.ISAAC.2018.22.pdf
- Filesize: 431 kB
- 12 pages
Document
Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
Authors
-
Part of:
Volume:
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-06
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.22
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- Distributed algorithms
- minor-closed family of graphs
- MDS
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
E. Szymańska A. Czygrinow, M. Hańćkowiak. Fast Distributed Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs. Proc. of 20th International Symposium, ISAAC, LNCS 5878, pages 668-678, 2009.
-
W. Wawrzyniak A. Czygrinow, M. Hańćkowiak. Fast distributed approximations in planar graphs. International Symposium on Distributed Computing, DISC, Arcachon, France, September 2008, LNCS 5218, pages 78-92, 2008.
-
R. Wattenhofer C. Lenzen. Minimum Dominating Set Approximation in Graphs of Bounded Arboricity. International Symposium on Distributed Computing, DISC 2010, pages 510-524, 2010.
-
R. Wattenhofer C. Lenzen, Y. A. Oswald. Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput., 26 (2), pages 119-137, 2013.
-
S. Gutner N. Alon. Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. Electronic Colloquium on Computational Complexity, Report No. 66, 2008.
-
S. Siebertz S. A. Amiri, S. Schmid. A Local Constant Factor MDS Approximation for Bounded Genus Graphs. PODC 2016, Proceedings of the ACM Symp. on Principles of Distributed Computing, 227-233, 2016.