Implementing Minimum Cycle Basis Algorithms
Kurt Mehlhorn, Dimitrios Michail · Lecture notes in computer science · 2005
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 efficient implementation of an O(m 3 + mn 2log n) 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 3) and O( m 2 n + mn 2 log n) respectively. Our experimental findings imply that the true bottleneck of a sophisticated implementation is the O( m 2 n + mn 2 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.Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis used in [1,2] and [3,4], to obtain a new hybrid algorithm with running time O(m 2 n 2). The hybrid algorithm is very efficient in practice for random dense unweighted graphs.Finally, we compare these two algorithms with a number of previous implementations for finding a minimum cycle basis in an undirected graph.