**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Thu, 24 Apr 2014 05:04:41 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*