Document Open Access Logo

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

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2021.59.pdf
  • Filesize: 0.7 MB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Distributed algorithms
  • f-matching
  • b-matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2021.59

Author Details

Andrzej Czygrinow
  • School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ, USA
Michał Hanćkowiak
  • Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland
Marcin Witkowski
  • Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland

Funding

  • Czygrinow, Andrzej: Research supported in part by Simons Foundation Grant # 521777.

References

  1. S. A. Amiri, S. Schmid, and S. Siebertz. Distributed dominating set approximations beyond planar graphs. ACM Transactions on Algorithms, Vol 15, Issue 3, 39:1-39:18., 2019. Google Scholar
  2. A. Czygrinow and M. Hanćkowiak. Distributed algorithm for better approximation of the maximum matching. Proc. Computing and Combinatorics: 9th Annual International Conference, COCOON 2003, 242-251., 2003. Google Scholar
  3. A. Czygrinow, M. Hańćkowiak, and E. Szymańska. A fast distributed algorithm for approximating the maximum matching. Proceedings of the Annual European Symposium on Algorithms (ESA), 2004, LNCS 3221, 252-263., 2004. Google Scholar
  4. A. Czygrinow, M. Hanćkowiak, and W. Wawrzyniak. Fast distributed approximations in planar graphs. International Symposium on Distributed Computing, DISC, Arcachon, France, September 2008, LNCS 5218, 78-92., 2008. Google Scholar
  5. M. Fischer. Improved deterministic distributed matching via rounding. 31st International Symposium on Distributed Computing (DISC 2017), LIPIcs 91, 17:1-17:15., 2017. Google Scholar
  6. M. Ghaffari, D. Harris, and F. Kuhn. On derandomizing local distributed algorithms. Proc. 59th IEEE Symposium on Foundations of Computer Science, 662-673., 2018. Google Scholar
  7. M. Hanćkowiak. Private communication. Google Scholar
  8. M. Hanćkowiak, M. Karoński, and A. Panconesi. On the distributed complexity of computing maximal matchings. Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 219-225., 1998. Google Scholar
  9. M. Hanćkowiak, M. Karoński, and A. Panconesi. A faster distributed algorithm for computing maximal matchings deterministically. Proc. of the ACM Symposium on Principles of Distributed Computing (PODC), 219-228., 1999. Google Scholar
  10. D. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. arXiv, 2018. URL: http://arxiv.org/abs/1807.07645.
  11. A. Kotlov. Short proof of the gallai-edmonds structure theorem. arXiv, 2000. URL: http://arxiv.org/abs/math/0011204.
  12. F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally? Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2004). New York, USA: ACM Press, 300-309., 2004. Google Scholar
  13. J. Nesetril and P. Ossona de Mendez. Sparsity: Graphs, structures, and algorithms. Algorithms and combinatorics 28, Springer, pp. I-XXIII, 1-457., 2012. Google Scholar
  14. D. Peleg. Distributed computing: A locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA., 2000. Google Scholar
  15. A. Shrijver. Combinatorial optimization. Springer, 2002. Google Scholar
  16. W.T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics 6, pp. 347–352., 1954. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact