A near-optimal parallel algorithm for edge-coloring outerplanar graphs
Y. Caspi, Eliezer Dekel · 2003
The article presents a parallel EREW PRAM algorithm that runs in O(log/sup 2/n) time using n/logn processors to optimally color the edges of an outerplanar graph. The algorithm improves the best known algorithm in both time, and number of processors. This more efficient algorithm is a result of a new approach for solving the problem. Also presented is a parallel EREW PRAM algorithm that runs in O(logn) using n/logn processors for finding a maximal matching in outerplanar graphs.>