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

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope