PARALLEL EDGE COLORING APPROXIMATION
Martin Fürer, Balaji Raghavachari · Parallel Processing Letters · 1996
Let G be a graph with n vertices and m edges and let its maximum degree be Δ. It is shown that a valid edge coloring of G using at most 2Δ−1 colors can be computed in O( log n log Δ) time using O(m+n) processors on a CREW PRAM. Based on this, for any constant c>1, a valid edge coloring for G using at most max([cΔ], Δ+1) colors can be computed in O( log 2 n) time, using O(m+n) processors. Employing different techniques, we show that it is possible to compute a Δ2 coloring in O( log * n) time, with O(m+n) processors. Also, a maximal matching of G can be computed in O( log 2 n log Δ) time using O(m+n) processors on a CREW PRAM.