DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.59

Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion

Authors: Andrzej Czygrinow, Michał Hanćkowiak, and Marcin Witkowski

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

We give a distributed algorithm which given ε > 0 finds a (1-ε)-factor approximation of a maximum f-matching in graphs G = (V,E) of sub-logarithmic expansion. Using a similar approach we also give a distributed approximation of a maximum b-matching in the same class of graphs provided the function b: V → ℤ^+ is L-Lipschitz for some constant L. Both algorithms run in O(log^* n) rounds in the LOCAL model, which is optimal.

Cite as

Andrzej Czygrinow, Michał Hanćkowiak, and Marcin Witkowski. Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{czygrinow_et_al:LIPIcs.ISAAC.2021.59,
  author =	{Czygrinow, Andrzej and Han\'{c}kowiak, Micha{\l} and Witkowski, Marcin},
  title =	{{Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.59},
  URN =		{urn:nbn:de:0030-drops-154925},
  doi =		{10.4230/LIPIcs.ISAAC.2021.59},
  annote =	{Keywords: Distributed algorithms, f-matching, b-matching}
}

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 Witkowski, Marcin

Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion

Abstract

Cite as

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