CISPA
Browse
cispa_all_3650.pdf (529.32 kB)

Distributed edge coloring in time polylogarithmic in Δ

Download (529.32 kB)
conference contribution
posted on 2023-11-29, 18:20 authored by Alkida Balliu, Sebastian BrandtSebastian Brandt, Fabian Kuhn, Dennis Olivetti
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].

History

Preferred Citation

Alkida Balliu, Sebastian Brandt, Fabian Kuhn and Dennis Olivetti. Distributed edge coloring in time polylogarithmic in Δ. In: ACM Symposium on Principles of Distributed Computing (PODC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)

Legacy Posted Date

2022-05-05

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3650, title = "Distributed edge coloring in time polylogarithmic in Δ", author = "Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis", booktitle="{ACM Symposium on Principles of Distributed Computing (PODC)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC