The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Yi‐Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, Yufan Zheng · 2019
In this paper, we present new randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (Δ+1)-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Δ + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log* Δ)-round randomized algorithms of Parter and Su [DISC'18] and O((log log Δ)⋅ log* Δ)-round randomized algorithm of Parter [ICALP'18].