|
|
| |
| 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
|
University of Bonn -> Department of Computer Science -> Chair V | |