A polynomial-time algorithm to find the shortest cycle basis of a graph
Loading...
Files
Date
1984
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.