EDGE-COLORING SERIES-PARALLEL GRAPHS

We present an algorithm for optimally edge coloring series parallel gr aphs. We give a linear time implementation, as well as a parallel impl ementation, of the algorithm that runs in O(log(3) n) time using O(n) processors. The sequential implementation, which is optimal, improves the best-known algorithm. The parallel implementation of the algorithm is the first known NC algorithm for this problem. The algorithm is ba sed on the ear decomposition of a graph (Y. Maon, B. Schieber, and U. Vishkin, Parallel ear decomposition search (EDS) and ST-Numbering in g raphs, Theoret. Comput. Sci. 47 (1986), 277-298). Eppstein (Parallel r ecognition of series-parallel graphs, Inform. Comput. 98 (1992), 41-55 ) found that any ear decomposition of a series parallel graph is neste d. We show constructively that for every biconnected series parallel g raph there exists an open ear decomposition, such that its correspondi ng tree of ears has an O(log n) depth, and this ear decomposition cont ains no ear whose endpoints are connected by a single edge in its pare nt. This result is used to reduce a match in series parallel graphs in to a match in outerplanar graphs, and to establish the edge coloring p roblem of series parallel graphs in NC. (C) 1995 Academic Press, Inc.