EUVIMEDEUVIMED entdecken
Crossref

Lower Bounds for Maximal Matchings and Maximal Independent Sets

Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela

Journal of the ACM · 31.10.2021 · 68 (5) · 1-30

DOI: 10.1145/3461458 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 06.12.2021. Verfasst von Alkida Balliu und 5 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: Academy of Finland, ESTATE.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O ( Δ + log * n ) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o (log * n ) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1-1/ n requires Ω (min { Δ , log log n / log log log n }) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω (min { Δ , log n / log log n }) rounds; this is an improvement over prior lower bounds also as a function of n .

Förderung

  • Academy of Finland
  • ESTATE

Zitieren

APA

Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., & Suomela, J. (2021). Lower Bounds for Maximal Matchings and Maximal Independent Sets. Journal of the ACM, 68(5), 1-30. https://doi.org/10.1145/3461458

Vancouver

Balliu A, Brandt S, Hirvonen J, Olivetti D, Rabie M, Suomela J. Lower Bounds for Maximal Matchings and Maximal Independent Sets. Journal of the ACM. 2021;68(5):1-30. doi:10.1145/3461458

BibTeX
@article{Balliu2021,
  author = {Balliu, Alkida and Brandt, Sebastian and Hirvonen, Juho and Olivetti, Dennis and Rabie, Mikaël and Suomela, Jukka},
  title = {Lower Bounds for Maximal Matchings and Maximal Independent Sets},
  journal = {Journal of the ACM},
  year = {2021},
  volume = {68},
  number = {5},
  pages = {1--30},
  doi = {10.1145/3461458}
}
Kostenlos starten →