Geodesic
Complexity Indices for the Traveling Salesman Problem Continued
Yugoslav journal of operations research, Tome 31 (2021) no. 4, p. 471 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

We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs $G$ with distances between cities as edge weights. A complexity index is an invariant of an instance $I$ by which we predict the execution time of an exact TSP algorithm for $I$. In the paper [5] we have considered some short edge sub-graphs of G and defined several new invariants related to their connected components. Extensive computational experiments with instances on 50 vertices with the uniform distribution of integer edge weights in the interval [1,100] show that there exists correlation between the sequences of selected invariants and the sequence of execution times of the well-known TSP Solver Concorde. In this paper we extend these considerations for instances up to 100 vertices.
Classification : 90C27, 05C80, 62H20
Keywords: Traveling salesman problem, Complexity index, Concorde TSP Solver, Random instances, Correlation. 
@article{YJOR_2021_31_4_a2,
     author = {Drago\v{s} Cvetkovi\'c and Zorica Dra\v{z}i\'c and Vera Kova\v{c}evi\'c-Vuj\v{c}i\'c},
     title = {Complexity {Indices} for the {Traveling} {Salesman} {Problem} {Continued}},
     journal = {Yugoslav journal of operations research},
     pages = {471 },
     year = {2021},
     volume = {31},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2021_31_4_a2/}
}
TY  - JOUR
AU  - Dragoš Cvetković
AU  - Zorica Dražić
AU  - Vera Kovačević-Vujčić
TI  - Complexity Indices for the Traveling Salesman Problem Continued
JO  - Yugoslav journal of operations research
PY  - 2021
SP  - 471 
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/YJOR_2021_31_4_a2/
LA  - en
ID  - YJOR_2021_31_4_a2
ER  - 
%0 Journal Article
%A Dragoš Cvetković
%A Zorica Dražić
%A Vera Kovačević-Vujčić
%T Complexity Indices for the Traveling Salesman Problem Continued
%J Yugoslav journal of operations research
%D 2021
%P 471 
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/YJOR_2021_31_4_a2/
%G en
%F YJOR_2021_31_4_a2
Dragoš Cvetković; Zorica Dražić; Vera Kovačević-Vujčić. Complexity Indices for the Traveling Salesman Problem Continued. Yugoslav journal of operations research, Tome 31 (2021) no. 4, p. 471 . http://geodesic.mathdoc.fr/item/YJOR_2021_31_4_a2/