(2022) Distributed edge coloring in time polylogarithmic in Δ.
|
Text
document.pdf Download (542kB) | Preview |
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 (2Δ-1)-edge coloring can be computed in time poly(log Δ) + O(log* 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 Δ. We further show that in the CONGEST model, an (8+epsilon)Δ-edge coloring can be computed in poly(log Δ) + O(log* n) rounds. The best previous O(Δ)-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it allows to compute a 2^{O(1/epsilon)}Δ-edge coloring in time O(Δ^epsilon + log* n) for any epsilon in (0,1].
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Sebastian Brandt (SB) |
| Conference: | PODC ACM Symposium on Principles of Distributed Computing |
| Depositing User: | Sebastian Brandt |
| Date Deposited: | 05 May 2022 10:40 |
| Last Modified: | 05 Sep 2022 13:57 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3650 |
Actions
Actions (login required)
 |
View Item |