Distributed Edge Coloring in Time Polylogarithmic in Δ

DOI10.1145/3519270.3538440arXiv2206.00976WikidataQ130835311 ScholiaQ130835311MaRDI QIDQ6201993FDOQ6201993

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)

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}^{*}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}^{*}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}^{*}n)$ for any $varepsilonin(0,1]$.

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

zbMATH Keywords

edge coloringlocal modelcongest modeltoken dropping

Mathematics Subject Classification ID

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

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)