AN EFFICIENT PARALLEL ALGORITHM FOR MAXIMUM MATCHING FOR SOME CLASSESOF GRAPHS

The P-4-tidy graphs were introduced by I. Rusu to generalize some alre ady known classes of graphs with few induced P-4 (cographs, P-4-sparse graphs, P-4-lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26-36.) on cographs, using the modular decomposition. As an application, we s how how to obtain a maximum matching parallel algorithm for the family of P-4-tidy graphs (represented by a parse tree) in O(log n) time wit h O(n/log n) processors in the EREW-PRAM model with n-vertex graphs. ( C) 1998 Academic Press, Inc.