Fast parallel algorithms for the approximate edge-coloring problem

This paper presents a parallel algorithm for the following problem: given a simple graph G(V,E), color its edges with max2^{i - 1} * (⌊ Δ 2^{i - 1}⌋ + 2),2^{i - 1} * (⌊ Δ 2^{i - 1}⌋ + 3) colors, 0 ≤ i ≤ ⌊logΔ⌋ - 1 such that all edges sharing a common vertex have different colors, where Δ ( = Δ(G)) is the maximum vertex degree, and |V| = n, |E| = m. This algorithm runs in O(( Δ 2^{i - 1})^3.5 log³ Δ log n + ( Δ 2^{i - 1})³ log⁴ n) time using O(maxn²,n( Δ 2^{i - 1})³) processors. Particularly, it only requires O(Δ^1.75 log³ Δ log n + Δ^1.5 log⁴ n) time and O(maxn²,nΔ^1.5) processors when we use Δ + √Δ colors to color G's edges. If we use 2.5Δ colors, it only requires O(log n log Δ) time and O(m) processors, based on a CREW PRAM. Unless otherwise specified, our computational model is a COMMON CRCW PRAM in which concurrent read and concurrent write are allowed. In addition, only writing the same value into a memory cell is successful when there exists write conflict. © 1995.