Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V