We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Edge-swapping algorithms for the minimum fundamental cycle basis problem.
- Authors
Amaldi, Edoardo; Liberti, Leo; Maffioli, Francesco; Maculan, Nelson
- Abstract
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.
- Subjects
GRAPH theory; SPANNING trees; ALGORITHMS; MATHEMATICAL variables; INTEGER programming; HEURISTIC programming
- Publication
Mathematical Methods of Operations Research, 2009, Vol 69, Issue 2, p205
- ISSN
1432-2994
- Publication type
Article
- DOI
10.1007/s00186-008-0255-4