b'@article{MM06,'b"\nTITLE = {Implementing Minimum Cycle Basis Algorithms},\nAUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios},\nLANGUAGE = {eng},\nLOCALID = {Local-ID: C1256428004B93B8-6975DD6D0B820206C125728E003E04A2-MM06},\nYEAR = {2006},\nDATE = {2006},\nABSTRACT = {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(m3 + mn2 log n) algorithm. For sparse graphs, this is the currently best-known algorithm. This algorithm's running time can be partitioned into two parts with time O(m3) and O(m2n + mn2 log n), respectively. Our experimental findings imply that for random graphs the true bottleneck of a sophisticated implementation is the O(m2 n + mn2 log n) part. A straightforward implementation would require $\\Omega$(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 speed-up. Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis to obtain a new hybrid algorithm with running time O(m2n2). 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 of an undirected graph.},\nJOURNAL = {ACM Journal of Experimental Algorithmics},\nVOLUME = {11},\nPAGES = {1--14},\n}\n"