b'@inproceedings{KMMP2004c,'b'\nTITLE = {A Faster Algorithm for Minimum Cycle Basis of Graphs},\nAUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios and Telikepalli, Kavitha and Paluch, Katarzyna},\nEDITOR = {D{\\\'i}az, Josep and Karhum{\\"a}ki, Juhani and Lepist{\\"o}, Arto and Sannella, Donald},\nLANGUAGE = {eng},\nISSN = {0302-9743},\nLOCALID = {Local-ID: C1256428004B93B8-158CD04BC22EDE8AC1256F4F00523BF7-KMMP2004c},\nPUBLISHER = {Springer},\nYEAR = {2004},\nDATE = {2004},\nABSTRACT = {In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result for this problem was an $O(m^{\\omega}n)$ algorithm, where $\\omega$ is the best exponent of matrix multiplication. It is presently known that $\\omega < 2.376$. We obtain an $O(m^2n + mn^2\\log n)$ algorithm for this problem. Our algorithm also uses fast matrix multiplication. When the edge weights are integers, we have an $O(m^2n)$ algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in $O(m^{\\omega})$ time. For any $\\epsilon > 0$, we also design a $1+\\epsilon$ approximation algorithm to compute a cycle basis which is at most $1+\\epsilon$ times the weight of a minimum cycle basis. The running time of this algorithm is $O(\\frac{m^{\\omega}}{\\epsilon}\\log(W/{\\epsilon}))$ for reasonably dense graphs, where $W$ is the largest edge weight.},\nBOOKTITLE = {Automata, languages and programming : 31st International Colloquium, ICALP 2004},\nPAGES = {846--857},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {3142},\n}\n'