2021/02/08 by Magnús M. Halldórsson, Halldórsson, Magnús M., Alexandre Nolin +1
Computer Science · Physics and Astronomy · #Color Science and Applications #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Image Enhancement Techniques #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2102.04546
openalex publication_date 2021/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a procedure for efficiently sampling colors in the \congest model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to Θ(log n) semi-random colors unused by their neighbors in O(1) rounds, even in the distance-2 setting. This yields algorithms with O(log^* Δ) complexity for different edge-coloring, vertex coloring, and distance-2 coloring problems, matching the best possible. In particular, we obtain an O(log^* Δ)-round CONGEST algorithm for (1+ε)Δ-edge coloring when Δ≥ log1+1/log^*n n, and a poly(loglog n)-round algorithm for (2Δ-1)-edge coloring in general. The sampling procedure is inspired by a seminal result of Newman in communication complexity.