Dahlhaus, E., Karpinski, M., and Lingas, A. (1989). A Parallel Algorithm for Maximum Matching in Planar Graphs. Technical Report LiTH-IDA-R-89-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We present a new parallel algorithm for finding a maximum cardinality matching in an arbitrary planar bipartite graph G. Our algorithm is processor-time efficient if the size l of a maximum cardinality matching of G is large. It runs in time O((0.5n -l+ sqrt (n)) (log n)**4) on a CRCW PRAM with O((n**1.5)log n) processors.
CS Dept TR Overview