A Parallel Algorithm for Maximum Matching in Planar Graphs

TitleA Parallel Algorithm for Maximum Matching in Planar Graphs
Publication TypeTechnical Report
Year of Publication1989
AuthorsKarpinski, M., Dahlhaus E., & Lingas A.
Other Numbers517
Abstract

We present a new parallel algorithm for finding a maximum (cardinality) matching in a planar bipartite graph G. Our algorithm is processor-time product efficient if the size l of a maximum matching of G is large. It runs in time O((n/2-l + (the square root of n))log (superscript 7)n) on a CRCW PRAM with O(n(superscript 1.5)log (superscript 3)n) processors.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-18.pdf
Bibliographic Notes

ICSI Technical Report TR-89-018

Abbreviated Authors

M. Karpinski, E. Dahlhaus, and A. Lingas

ICSI Publication Type

Technical Report