Geodesic
Mathematical Models and a Constructive Heuristic for Finding Minimum Fundamental Cycle Bases
Yugoslav journal of operations research, Tome 15 (2005) no. 1, p. 15 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

The problem of finding a fundamental cycle basis with minimum total cost in a graph arises in many application fields. In this paper we present some integer linear programming formulations and we compare their performances, in terms of instance size, CPU time required for the solution, and quality of the associated lower bound derived by solving the corresponding continuous relaxations. Since only very small instances can be solved to optimality with these formulations and very large instances occur in a number of applications, we present a new constructive heuristic and compare it with alternative heuristics.
Keywords: Fundamental cycle, cycle basis, IP formulation, tree-growing heuristic. 
@article{YJOR_2005_15_1_a1,
     author = {Leo Liberti and Edoardo Amaldi and Francesco Maffioli and Nelson Maculan},
     title = {Mathematical {Models} and a {Constructive} {Heuristic} for {Finding} {Minimum} {Fundamental} {Cycle} {Bases}},
     journal = {Yugoslav journal of operations research},
     pages = {15 },
     year = {2005},
     volume = {15},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2005_15_1_a1/}
}
TY  - JOUR
AU  - Leo Liberti
AU  - Edoardo Amaldi
AU  - Francesco Maffioli
AU  - Nelson Maculan
TI  - Mathematical Models and a Constructive Heuristic for Finding Minimum Fundamental Cycle Bases
JO  - Yugoslav journal of operations research
PY  - 2005
SP  - 15 
VL  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2005_15_1_a1/
LA  - en
ID  - YJOR_2005_15_1_a1
ER  - 
%0 Journal Article
%A Leo Liberti
%A Edoardo Amaldi
%A Francesco Maffioli
%A Nelson Maculan
%T Mathematical Models and a Constructive Heuristic for Finding Minimum Fundamental Cycle Bases
%J Yugoslav journal of operations research
%D 2005
%P 15 
%V 15
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2005_15_1_a1/
%G en
%F YJOR_2005_15_1_a1
Leo Liberti; Edoardo Amaldi; Francesco Maffioli; Nelson Maculan. Mathematical Models and a Constructive Heuristic for Finding Minimum Fundamental Cycle Bases. Yugoslav journal of operations research, Tome 15 (2005) no. 1, p. 15 . http://geodesic.mathdoc.fr/item/YJOR_2005_15_1_a1/