b'@article{Mehlhorn2007b,'b"\nTITLE = {Implementing Minimum Cycle Basis Algorithms},\nAUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios},\nLANGUAGE = {eng},\nISSN = {1084-6654},\nDOI = {10.1145/1187436.1216582},\nLOCALID = {Local-ID: C12573CC004A8E26-7809D4DD4F26C131C125729C0046E9A4-Mehlhorn2007b},\nPUBLISHER = {ACM},\nADDRESS = {New York, N.Y.},\nYEAR = {2007},\nDATE = {2007},\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 = {Journal of Experimental Algorithmics},\nVOLUME = {11},\nPAGES = {2.5.1--2-5-14},\n}\n"