EUVIMEDEUVIMED entdecken
Crossref

Distributed Edge Coloring in Time Polylogarithmic in \({\Delta }\)

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti

SIAM Journal on Computing · 31.08.2026 · 55 (4) · 592-621

DOI: 10.1137/24m1715866 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 23.07.2026. Verfasst von Alkida Balliu und 3 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a [Formula: see text]-edge coloring can be computed in time [Formula: see text] in the [Formula: see text] model. This improves a result of Balliu, Kuhn, and Olivetti [ Distributed edge coloring in time quasi-polylogarithmic in [Formula: see text], in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020, pp. 289–298], who gave an algorithm with a quasi-polylogarithmic dependency on [Formula: see text]. We further show that in the [Formula: see text] model, an [Formula: see text]-edge coloring can be computed in [Formula: see text] rounds. The best previous [Formula: see text]-edge coloring algorithm that can be implemented in the [Formula: see text] model is by Barenboim and Elkin [ J. ACM, 58 (2011), 23] and it computes a [Formula: see text]-edge coloring in time [Formula: see text] for any [Formula: see text].

Zitieren

APA

Balliu, A., Brandt, S., Kuhn, F., & Olivetti, D. (2026). Distributed Edge Coloring in Time Polylogarithmic in \({\Delta }\). SIAM Journal on Computing, 55(4), 592-621. https://doi.org/10.1137/24m1715866

Vancouver

Balliu A, Brandt S, Kuhn F, Olivetti D. Distributed Edge Coloring in Time Polylogarithmic in \({\Delta }\). SIAM Journal on Computing. 2026;55(4):592-621. doi:10.1137/24m1715866

BibTeX
@article{Balliu2026,
  author = {Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis},
  title = {Distributed Edge Coloring in Time Polylogarithmic in \(\Delta \)},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {4},
  pages = {592--621},
  doi = {10.1137/24m1715866}
}
Kostenlos starten →