| An Õ(m2 n) algorithm for Minimum Cycle Basis of graphs ∗ (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The input to this problem is an undirected graph whose edges have non-negative weights. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F2 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 weights of the cycles is minimum is called a minimum cycle basis of G. Apart from its interest as a natural question, the problem of efficiently computing a minimum cycle basis is motivated by its use as a preprocessing step in several algorithms. The previous best result for computing a minimum cycle basis in an undirected graph was an O(m ω n) algorithm, where ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. We obtain an O(m 2 n + mn 2 log n) algorithm for this problem. When the edge weights are integers, we have an O(m 2 n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ω) time. For any ɛ> 0, we also design a 1 + ɛ approximation algorithm to compute a cycle basis which is at most 1 + ɛ times the weight of a minimum cycle basis. The running time of this algorithm is O ( mω ɛ log(W/ɛ)) for reasonably dense graphs, where W is the largest edge weight. | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||