Once again: Finding simple cycles in graphs
Carsten Dorgerloh, J urgen Wirtgen · 1997
We present a randomized algorithm that computes a simple cycle of length k in general graphs, where k is a fixed integer, in O(maxfm;n log ng) 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(maxfm log n; n log ng) 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 [AYZ 94], whether deciding if a given graph contains a triangle is as difficult as boolean multiplication of two n by n matrices, in the negative. x Institut fur Informatik V, Universitat Bonn, Romerstr. 164, D-53117 Bonn, Germany, email: [email protected] -- Institut fur Informatik V, Universitat Bonn, Romerstr. 164, D-53117 Bonn, Germany, email: [email protected] 1 Introduction It is well known that finding the longest cycle in a graph is a hard problem, since finding a hamiltoni...