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

Loading...
Thumbnail Image

Date

1984

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.

Description

Keywords

Citation

Collections