A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph

Define the length of a basis of the cycle space of a graph to be the sum of the lengths of all cycles in the basis. An algorithm is given that finds a cycle basis with the shortest possible length in O(m³ n) operations, where m is the number of edges and n is the number of vertices. This is the first known polynomial-time algorithm for this problem. Edges may be weighted or unweighted. Also, the shortest cycle basis is shown to have at most 3(n - 1)(n - 2) / 2 edges for the unweighted case. O(mn² ) algorithm to obtain a suboptimal cycle basis of length O(n² ) for unweighted graphs is also given.