Improved distributed $$\Delta $$-coloring

Mohsen Ghaffari, Juho Hirvonen, Fabian Kühn, Yannic Maus

Type: Article

Publication Date: 2021-07-09

Citations: 4

DOI: https://doi.org/10.1007/s00446-021-00397-4

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).

Locations

Distributed Computing - View - PDF
PubMed Central - View
arXiv (Cornell University) - View - PDF
Europe PMC (PubMed Central) - View - PDF
Aaltodoc (Aalto University) - View - PDF
Repository for Publications and Research Data (ETH Zurich) - View - PDF
PubMed - View

Similar Works

Action	Title	Year	Authors
+	Improved Distributed $Δ$-Coloring	2018	Mohsen Ghaffari Juho Hirvonen Fabian Kühn Yannic Maus
+ PDF Chat	Improved Distributed Delta-Coloring	2018	Mohsen Ghaffari Juho Hirvonen Fabian Kühn Yannic Maus
+	Distributed $(Δ+1)$-Coloring in Sublogarithmic Rounds	2016	David G. Harris Johannes Schneider Hsin-Hao Su
+	$(Δ+1)$ Coloring in the Congested Clique Model	2018	Merav Parter
+	Locally-iterative $(Δ+1)$-Coloring in Sublinear (in $Δ$) Rounds	2022	Xinyu Fu Yitong Yin Chaodong Zheng
+	Coloring Fast with Broadcasts	2023	Maxime Flin Mohsen Ghaffari Magnús M. Halldórsson Fabian Kühn Alexandre Nolin
+	Distributed coloring of graphs with an optimal number of colors	2018	Étienne Bamas Louis Esperet
+	$(\Delta+1)$ Coloring in the Congested Clique Model	2018	Merav Parter
+	Distributed Edge Coloring in Time Polylogarithmic in $Δ$	2022	Alkida Balliu Sebastian Brandt Fabian Kühn Dennis Olivetti
+	Coloring Fast Without Learning Your Neighbors' Colors	2020	Magnús M. Halldórsson Fabian Kühn Yannic Maus Alexandre Nolin
+	Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition	2020	Mohsen Ghaffari Fabian Kühn
+ PDF Chat	Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time	2014	Leonid Barenboim Michael Elkin Fabian Kühn
+	Fully Dynamic $(Δ+1)$-Coloring in Constant Update Time	2019	Sayan Bhattacharya Fabrizio Grandoni Janardhan Kulkarni Quanquan C. Liu Shay Solomon
+	Fully Dynamic $(Δ+1)$-Coloring in Constant Update Time	2019	Sayan Bhattacharya Fabrizio Grandoni Janardhan Kulkarni Quanquan C. Liu Shay Solomon
+	Coloring Fast Without Learning Your Neighbors' Colors	2020	Magnús M. Halldórsson Fabian Kühn Yannic Maus Alexandre Nolin
+	Improved distributed degree splitting and edge coloring	2017	Mohsen Ghaffari Juho Hirvonen Fabian Kühn Yannic Maus Jukka Suomela Jara Uitto
+ PDF Chat	Distributed Graph Coloring Made Easy	2023	Yannic Maus
+ PDF Chat	Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition	2022	Mohsen Ghaffari Fabian Kühn
+ PDF Chat	Near-optimal distributed degree+1 coloring	2022	Magnús M. Halldórsson Fabian Kühn Alexandre Nolin Tigran Tonoyan
+	Faster Deterministic Distributed Coloring Through Recursive List Coloring	2019	Fabian Kühn

Works That Cite This (4)

Action	Title	Year	Authors
+ PDF Chat	Distributed Lower Bounds for Ruling Sets	2020	Alkida Balliu Sebastian Brandt Dennis Olivetti
+ PDF Chat	Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics	2021	Jan Grebík Václav Rozhoň
+	Distributed Symmetry Breaking on Power Graphs via Sparsification	2023	Yannic Maus Saku Peltonen Jara Uitto
+	Efficient CONGEST Algorithms for the Lovasz Local Lemma	2021	Yannic Maus Jara Uitto

Works Cited by This (17)

Action	Title	Year	Authors
+ PDF Chat	Brooks' Theorem and Beyond	2014	Daniel W. Cranston Landon Rabern
+	A fast and simple randomized parallel algorithm for the maximal independent set problem	1986	Noga Alon László Babai Alon Itai
+ PDF Chat	The Locality of Distributed Symmetry Breaking	2012	Leonid Barenboim Michael Elkin Seth Pettie Johannes Schneider
+ PDF Chat	A lower bound for the distributed Lovász local lemma	2016	Sebastian Brandt Orr Fischer Juho Hirvonen Barbara Keller Tuomo Lempiäinen Joel Rybicki Jukka Suomela Jara Uitto
+ PDF Chat	The Locality of Distributed Symmetry Breaking	2016	Leonid Barenboim Michael Elkin Seth Pettie Johannes Schneider
+ PDF Chat	On the complexity of local distributed graph problems	2017	Mohsen Ghaffari Fabian Kühn Yannic Maus
+	An Optimal Distributed $(\Delta+1)$-Coloring Algorithm?	2017	Yi‐Jun Chang Wenzheng Li Seth Pettie
+	Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models	2017	Leonid Barenboim Michael Elkin Uri Goldenberg
+ PDF Chat	Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model	2019	Shiri Chechik Doron Mukhtar
+	Distributed Degree Splitting, Edge Coloring, and Orientations	2017	Mohsen Ghaffari Hsin-Hao Su