Improved distributed [Delta]-coloring
Abstract: We present a randomized distributed algorithm that computes a Δ-coloring in any non-complete graph with maximum degree Δ≥4 in O(logΔ)+2O(loglogn√) rounds, as well as a randomized algorithm that computes a Δ-coloring in O((loglogn)2) rounds when Δ∈[3,O(1)]. Both these algorithms improve on an O(log3n/logΔ)-round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Ω(loglogn) round lower bound of Brandt et al. (STOC’16)
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Notes
-
Distributed computing. - 34, 4 (2021) , 239-258, ISSN: 1432-0452
- Event
-
Veröffentlichung
- (where)
-
Freiburg
- (who)
-
Universität
- (when)
-
2021
- Creator
- DOI
-
10.1007/s00446-021-00397-4
- URN
-
urn:nbn:de:bsz:25-freidok-2198048
- Rights
-
Kein Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
14.08.2025, 10:47 AM CEST
Data provider
This object is provided by:
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Ghaffari, Mohsen
- Hirvonen, Juho
- Kuhn, Fabian
- Maus, Yannic
- Universität
Time of origin
- 2021
Other Objects (12)
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Coloring Graphs in Oriented Coloring of Cubic Graphs
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Cunt Coloring Book.
SCHWARZKOPF IGORA COLORING
SCHWARZKOPF IGORA COLORING
Dynamic Graph Coloring
Balanced interval coloring
Selfish Bin Coloring
Political ecologies of resettlement in river deltas
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Coloring Graphs in Oriented Coloring of Cubic Graphs
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Cunt Coloring Book.
SCHWARZKOPF IGORA COLORING
SCHWARZKOPF IGORA COLORING
Dynamic Graph Coloring
Balanced interval coloring
Selfish Bin Coloring
Political ecologies of resettlement in river deltas
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Coloring Graphs in Oriented Coloring of Cubic Graphs
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Cunt Coloring Book.
SCHWARZKOPF IGORA COLORING
SCHWARZKOPF IGORA COLORING
Dynamic Graph Coloring
Balanced interval coloring
Selfish Bin Coloring