Parallel algorithms for the edge-coloring and edge-coloring update problems

Let G(V, E) be a simple undirected graph with a maximum vertex degree Δ(G) (or Δ for short), |V| = n and |E| = m. An edge-coloring of G is an assignment to each edge in G a color such that all edges sharing a common vertex have different colors. The minimum number of colors needed is denoted by X'(G) (called the chromatic index). For a simple graph G, it is known that Δ ≤ X'(G) ≤ Δ + 1. This paper studies two edge-coloring problems. The first problem is to perform edge-coloring for an existing edge-colored graph G with Δ + 1 colors stemming from the addition of a new vertex into G. The proposed parallel algorithm for this problem runs in O(Δ^3/2 log³ Δ + Δ log n) time using O(max{nΔ, Δ³}) processors. The second problem is to color the edges of a given uncolored graph G with Δ + 1 colors. For this problem, our first parallel algorithm requires O(Δ^5.5 log³ Δ log n + Δ⁵ log⁴ n) time and O(max{n²Δ, nΔ³}) processors, which is a slight improvement on the algorithm by H. J. Karloff and D. B. Shmoys [J. Algorithms 8 (1987), 39-52]. Their algorithm costs O(Δ⁶ log⁴ n) time and O(n²Δ) processors if we use the fastest known algorithm for finding maximal independent sets by M. Goldberg and T. Spencer [SIAM J. Discrete Math. 2 (1989), 322-328]. Our second algorithm requires O(Δ^4.5 log³ Δ log n + Δ⁴ log⁴ n) time and O(max{n², nΔ³}) processors. Finally, we present our third algorithm by incorporating the second algorithm as a subroutine. This algorithm requires O(Δ^3.5 log³ Δ log n + Δ³ log⁴ n) time and O(max{n² log Δ, nΔ³}) processors, which improves, by an O(Δ^2.5) factor in time, on Karloff and Shmoys' algorithm. All of these algorithms run in the COMMON CRCW PRAM model. © 1996 Academic Press, Inc.