@inbook{2e5ca690b1974c7e95115012a8b0eace,
title = "Efficient edge-swapping heuristics for finding minimum fundamental cycle bases",
abstract = "The problem of finding a fundamental cycle basis with minimum total cost in a graph is NP-hard. Since fundamental cycle bases correspond to spanning trees, we propose new heuristics (local search and metaheuristics) in which edge swaps are iteratively applied to a current spanning tree. Structural properties that make the heuristics efficient are established. We also present a mixed integer programming formulation of the problem whose linear relaxation yields tighter lower bounds than known formulations. Computational results obtained with our algorithms are compared with those from existing constructive heuristics on several types of graphs.",
author = "Edoardo Amaldi and Leo Liberti and Nelson Maculan and Francesco Maffioli",
year = "2004",
month = jan,
day = "1",
doi = "10.1007/978-3-540-24838-5\_2",
language = "English",
isbn = "3540220674",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "14--29",
editor = "Ribeiro, \{Celso C.\} and Martins, \{Simone L.\}",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}