Distributed Edge Coloring in Time Polylogarithmic in Δ

DOI10.1145/3519270.3538440MaRDI QIDQ6201993zbMATH OpenWikidataFDO

Authors Alkida Balliu, Sebastian F. Brandt, Fabian Kuhn, Dennis Olivetti

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.00976

zbMATH Keywords

congest modeledge coloringlocal modeltoken dropping

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: 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 $(2Delta-1)$-edge coloring can be computed in time $mathrmpolylogDelta+O(lo{g}^{\ast }n)$ in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on $Delta$. We further show that in the CONGEST model, an $(8+varepsilon)Delta$-edge coloring can be computed in $mathrmpolylogDelta+O(lo{g}^{\ast }n)$ rounds. The best previous $O(Delta)$-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a $2^{O(1/varepsilon)}Delta$-edge coloring in time $O(Delt{a}^{v}arepsilon+lo{g}^{\ast }n)$ for any $varepsilonin(0,1]$.

Cited in

(4)

• Brief announcement: Simpler and more general distributed coloring based on simple list defective coloring algorithms
• Faster edge coloring by partition sieving
• Vizing's theorem in near-linear time
• Improved streaming edge coloring

This page was built for publication: Distributed Edge Coloring in Time Polylogarithmic in Δ

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201993)