|
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 |