
University of Bonn > Department of Computer Science > Chair V  
CSReports 1997  Copyright 1997 University of Bonn, Department of Computer Science, 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\})$ worstcase 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 