Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
8532

10.12.2008

A Parallel Algorithm for Maximum Matching in Planar Graphs
Elias Dahlhaus, Marek Karpinski and Andrzej Lingas
[Download PostScript] [Download PDF]

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 0((n/2-l+n1/2)log7n) on a CRCW PRAM with O(n1.5log3n) processors.

Last Change: 12/10/08 at 15:32:41
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope