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^3 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^2 )$ algorithm to obtain a suboptimal cycle basis of length $O(n^2 )$ for unweighted graphs is also given.