Algorithms for finding minimum fundamental cycle bases in graphs

We describe new heuristics for solving the problem of finding the fundamental cycle bases of minimum cost in a simple, undirected, biconnected graph G. Since each spanning tree of G is associated to a fundamental cycle basis, edge swaps are iteratively performed on the current spanning tree so as to improve the cost of the corresponding fundamental cycle basis. Furthermore, we establish graph-theoretical structural results that allow an efficient implementation of our algorithms.