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

IDA Technical Reports: abstract

Generated: Sat, 01 Nov 2014 12:10:39

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>