Edge-swapping algorithms for the minimum fundamental cycle basis problem

We consider the problem of finding a fundamental cycle basis with minimum total cost in an undirected graph. This problem is NP-hard and has several interesting applications. Since fundamental cycle bases correspond to spanning trees, we propose a local search algorithm, a tabu search and variable neighborhood search in which edge swaps are iteratively applied to a current spanning tree. We also present a mixed integer programming formulation of the problem whose linear relaxation yields tighter lower bounds than other known formulations. Computational results obtained with our algorithms are compared with those from the best available constructive heuristic on several types of graphs. This article extends the conference paper (Amaldi et al. 2004).