|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 1990 | Copyright 1990 University of Bonn, Department of Computer Science, Abt. V | |
|
8549 20.11.2008 |
Nearly Optimal Parallel Algorithm for Maximum Matching in Planar Graphs
Ming Kao, Marek Karpinski, Andrzej Lingas [Download PostScript] [Download PDF] We present a nearly optimal parallel algorithm for finding a maximum (cardinality) matching in a planar bipartite graph G. Let ε be an arbitrarily small posite real. It runs in time O(n1/2 log6n) on a probabilistic CRCW PRAM with O(n1+ε) processors. |
|
|
Last Change:
11/20/08 at 13:08:41
|
University of Bonn -> Department of Computer Science -> Chair V | |