Abstract
In this article, we present a deterministic CONGEST algorithm to compute an O(kΔ)-vertex coloring in O(Δ/k) + log ∗ n rounds, where Δ is the maximum degree of the network graph and k ≥ 1 can be freely chosen. The algorithm is extremely simple: each node locally computes a sequence of colors and then it tries colors from the sequence in batches of size k. Our algorithm subsumes many important results in the history of distributed graph coloring as special cases, including Linial’s color reduction [Linial, FOCS’87], the celebrated locally iterative algorithm from [Barenboim, Elkin, Goldenberg, PODC’18], and various algorithms to compute defective and arbdefective colorings. Our algorithm can smoothly scale between several of these previous results and also simplifies the state-of-the-art (Δ + 1)-coloring algorithm. At the cost of losing some of the algorithm’s simplicity we also provide a O(kΔ)-coloring algorithm in O(√Δ/k) + log ∗ n rounds. We also provide improved deterministic algorithms for ruling sets, and, additionally, we provide a tight characterization for one-round color reduction algorithms.
Original language | English |
---|---|
Article number | 21 |
Pages (from-to) | 21:1-21:21 |
Number of pages | 21 |
Journal | ACM Transactions on Parallel Computing |
Volume | 10 |
Issue number | 4 |
DOIs | |
Publication status | Published - 14 Dec 2023 |
Keywords
- CONGEST model
- distributed graph coloring
- LOCAL model
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Science Applications
- Computational Theory and Mathematics
- Modelling and Simulation