Distributed Edge Coloring in Time Polylogarithmic in \({\Delta }\)
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.
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}
}
EUVIMED