b'@inproceedings{MM05,'b"\nTITLE = {Implementing Minimum Cycle Basis Algorithms},\nAUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios},\nEDITOR = {Nikoletseas, Sotiris},\nLANGUAGE = {eng},\nISBN = {3-540-25920-1},\nLOCALID = {Local-ID: C1256428004B93B8-AC9540F47424F880C1256FD400450006-MM05},\nPUBLISHER = {Springer},\nYEAR = {2005},\nDATE = {2005},\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(m^3 + mn^2\\log n)$ algorithm presented in~\\cite{PINA95}. 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^2n + 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 $\\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 speedup. Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis used in~\\cite{PINA95,KMMP04} and~\\cite{HOR87,MATR02}, 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.},\nBOOKTITLE = {Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005},\nPAGES = {32--43},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {3503},\n}\n"