About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Edge coloring series parallel graphs
Abstract
We present an algorithm for optimally edge coloring series parallel graphs. We give a linear time implementation, as well as a parallel implementation, of the algorithm that runs in O(log3n) 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 based on the ear decomposition of a graph (Y. Maon, B. Schieber, and U. Vishkin, Parallel ear decomposition search (EDS) and ST-Numbering in graphs, Theoret. Comput. Sci.47 (1986), 277-298). Eppstein (Parallel recognition of series-parallel graphs, Inform. Comput.98 (1992), 41-55) found that any ear decomposition of a series parallel graph is nested. We show constructively that for every biconnected series parallel graph there exists an open ear decomposition, such that its corresponding tree of ears has an O(log n) depth, and this ear decomposition contains no ear whose endpoints are connected by a single edge in its parent. This result is used to reduce a match in series parallel graphs into a match in outerplanar graphs, and to establish the edge coloring problem of series parallel graphs in NC. © 1995 Academic Press, Inc.