Minimum cycle basis: algorithms and applications

We consider the problem of computing a minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices. 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 of its cycle space. A cycle basis where the sum of the weights of its cycles is minimum is called a minimum cycle basis of G. Minimum cycle bases are useful in a number of contexts, e.g., the analysis of electrical networks, structural engineering, and chemistry. We present an O(m 2 n + mn 2 log n) algorithm to compute a minimum cycle basis. The previously best known running time to compute a minimum cycle basis was O(m ω n), where ω is the exponent of matrix multiplication. It is presently known that ω < 2.376. When the edge weights are integers, we give an O(m 2 n) algorithm. For unweighted graphs which are reasonabl