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 + ε)Δ-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 computes a 2O(1/ε)Δ- edge coloring in time O(Δε + log* n) for any ε ∈ (0, 1].

Distributed Edge Coloring in Time Polylogarithmic in Δ

Balliu, Alkida;Olivetti, Dennis
2022-01-01

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 + ε)Δ-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 computes a 2O(1/ε)Δ- edge coloring in time O(Δε + log* n) for any ε ∈ (0, 1].
2022
9781450392624
edge coloring, LOCAL model, CONGEST model, token dropping
File in questo prodotto:
File Dimensione Formato  
2022_PODC2022_15_Balliu.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 1.45 MB
Formato Adobe PDF
1.45 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/25946
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 2
social impact