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)
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Anmerkungen
-
Distributed computing. - 34, 4 (2021) , 239-258, ISSN: 1432-0452
- Ereignis
-
Veröffentlichung
- (wo)
-
Freiburg
- (wer)
-
Universität
- (wann)
-
2021
- Urheber
- DOI
-
10.1007/s00446-021-00397-4
- URN
-
urn:nbn:de:bsz:25-freidok-2198048
- Rechteinformation
-
Kein Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
25.03.2025, 13:46 MEZ
Datenpartner
Dieses Objekt wird bereitgestellt von:
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
- Ghaffari, Mohsen
- Hirvonen, Juho
- Kuhn, Fabian
- Maus, Yannic
- Universität
Entstanden
- 2021
Ähnliche Objekte (12)
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Political ecologies of resettlement in river deltas
Improved virtual orbitals for charge transfer excitations in TDDFT
Die wirtschaftliche Regionalentwicklung zwischen dem Amu-Darja-Delta und Westkazachstan unter dem Einfluss des Eisenbahnbaus
Design study of high-speed continuous-time delta-sigma modulator
Specifying and model checking distributed control algorithms at meta-level
Improved virtual orbitals for charge transfer excitations in time dependent DFT
Charge transfer excitations with range separated functionals using improved virtual orbitals
Delta-4 : a generic architecture for dependable distributed computing
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Political ecologies of resettlement in river deltas
Improved virtual orbitals for charge transfer excitations in TDDFT
Die wirtschaftliche Regionalentwicklung zwischen dem Amu-Darja-Delta und Westkazachstan unter dem Einfluss des Eisenbahnbaus
Design study of high-speed continuous-time delta-sigma modulator
Specifying and model checking distributed control algorithms at meta-level
Improved virtual orbitals for charge transfer excitations in time dependent DFT
Charge transfer excitations with range separated functionals using improved virtual orbitals
Delta-4 : a generic architecture for dependable distributed computing
Improved distributed fractional coloring algorithms
Ilias diachronica Delta (4)
Ilias diachronica Delta (4)
Sampling soil water along the pF curve for [delta]2H and [delta]18O analysis
Political ecologies of resettlement in river deltas
Improved virtual orbitals for charge transfer excitations in TDDFT
Die wirtschaftliche Regionalentwicklung zwischen dem Amu-Darja-Delta und Westkazachstan unter dem Einfluss des Eisenbahnbaus
Design study of high-speed continuous-time delta-sigma modulator
Specifying and model checking distributed control algorithms at meta-level
Improved virtual orbitals for charge transfer excitations in time dependent DFT
Charge transfer excitations with range separated functionals using improved virtual orbitals