A polynomial-time algorithm to find the shortest cycle basis of a graph

Abstract

Define the length of a basis of a cycle space to be the sum of the lengths of all circuits in the basis. An algorithm is given that finds a basis with the shortest length in 0(e[superscript 3]v) operations. Edges may be weighted or unweighted.