b'@inproceedings{KMM07,'b'\nTITLE = {New Approximation Algorithms for Minimum Cycle Bases of Graphs},\nAUTHOR = {Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios},\nLANGUAGE = {eng},\nISBN = {978-3-540-70917-6},\nDOI = {10.1007/978-3-540-70918-3_44},\nLOCALID = {Local-ID: C12573CC004A8E26-2BFAB74EC24AD32DC125728E003EAFF1-KMM07},\nPUBLISHER = {Springer},\nYEAR = {2007},\nDATE = {2007},\nABSTRACT = {We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g.\xc2\xa0the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k\\,$\\geq$\\,1, we give (2k\\,{\\textminus}\\,1)-approximation algorithms with expected running time O(k m n1\\,+\\,2/k\\,+\\,m n(1\\,+\\,1/k)($\\omega$\\,{\\textminus}\\,1)) and deterministic running time O( n3\\,+\\,2/k ), respectively. Here $\\omega$ is the best exponent of matrix multiplication. It is presently known that $\\omega$\\,<\\,2.376. Both algorithms are o( m$\\omega$ ) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the $\\Theta$(m$\\omega$) bound. We also present a 2-approximation algorithm with expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.},\nBOOKTITLE = {STACS 2007},\nEDITOR = {Thomas, Wolfgang and Weil, Pascal},\nPAGES = {512--523},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {4393},\nADDRESS = {Aachen, Germany},\n}\n'