Prof. Michael Elkin

We study the (Δ+ 1)-edge-coloring problem in the parallel (PRAM) model of computation. The celebrated Vizing's theorem [Viz64] states that every simple graph G = (V, E) can be properly (Δ+ 1)-edge-colored. In a seminal paper, Karloff and Shmoys [KS87] devised a parallel algorithm with time O(δ⁵ · log n · (log³ n + δ²)) and O(m · δ) processors. This result was improved by Liang et al. [LSH96] to time O(δ^4.5 · log³ Δ· log n + δ⁴ · log⁴n) and O(n •δ³ + n²) processors. [LSH96] claimed O(δ^3.5 · log³ Δ· log n + δ³ •log⁴ n) time, but we point out a flaw in their analysis, which once corrected, results in the above bound. We devise a faster parallel algorithm for this fundamental problem. Specifically, our algorithm uses O(δ⁴ · log⁴ n) time and O(m · δ) processors. Another variant of our algorithm requires O(δ^4+o(1) · log² n) time, and [EQUATION] processors, for an arbitrarily small δ > 0. We also devise a few other tradeoffs between the time and the number of processors, and devise an improved algorithm for graphs with small arboricity. On the way to these results, we also provide a very fast parallel algorithm for updating (Δ+ 1)-edge-coloring. Our algorithm for this problem is dramatically faster and simpler than the previous state-of-the-art algorithm (due to [LSH96]) for this problem.