Very fast parallel algorithms for approximate edge coloring
This paper presents very fast parallel algorithms for approximate edge coloring. Let , and . It is shown that a graph with n vertices and m edges can be edge colored with colors in time using O(m+n) processors on the EREW PRAM, where ? is the maximum vertex degree of the graph and c is an arbitrarily large constant. It is also shown that the graph can be edge colored using at most colors in time using O(m+n) processors on the same model.
parallel algorithms edge coloring pram analysis of algorithms graph algorithms