Implementing Minimum Cycle Basis Algorithms

In this paper we consider the problem of computing a minimum cycle basis of an undirected graph G = (V, E) with n vertices and m edges. We describe an e#cient implementation of an O(m algorithm presented in [1]. For sparse graphs this is the currently best known algorithm. This algorithm's running time can be partitioned into two parts with time O(m ) and O(m log n) respectively. Our experimental findings imply that the true bottleneck of a sophisticated implementation is the O(m log n) part. A straightforward implementation would require# (nm) shortest path computations, thus we develop several heuristics in order to get a practical algorithm. Our experiments show that in random graphs our techniques result in a significant speedup