Institut für Informatik
 
Abteilung V

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

Once again: Finding simple cycles in graphs
Carsten Dorgerloh, Juergen Wirtgen
[Download PostScript] [Download PDF]

We present a randomized algorithm that computes a simple cycle of length $k$ in general graphs, where $k$ is a fixed integer, in $\O$$(\max\{m, n \log n\})$ expected time. This algorithm can be derandomized with only a small loss in efficiency, yielding a deterministic algorithm for this task which runs in $\O$$(\max\{m \log n, n \log n\})$ worst-case time. We show that the randomized algorithm may be parallelized. These algorithms improve upon previous results of many authors. Furthermore, we answer the question of \cite{AlYuZw94}, whether deciding if a given graph contains a triangle is as difficult as boolean multiplication of two $n$ by $n$ matrices, in the negative.

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