Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V
85150

A Fast Randomized Parallel Algorithm for Finding Simple Cycles in Planar Graphs
Carsten Dorgerloh
[Download PostScript] [Download PDF]

We show that if a planar graph has a simple cycle of length $k$, where $k$ is a fixed integer, such a cycle may be computed in $\O$$(\log n \log^* n)$ expected time by a randomized EREW-PRAM with $\O$$(n)$ processors.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V