Geodesic
The traveling salesman problem: The spectral radius and the length of an optimal tour
Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 43 (2018), p. 18 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

We consider the symmetric traveling salesman problem $($TSP$)$ with instances represented by complete graphs with distances between cities as edge weights. Computational experiments with randomly generated instances on $50$ and $100$ vertices with the uniform distribution of integer edge weights in interval $[1,100]$ show that there exists a correlation between the sequences of the spectral radii of the distance matrices and the lengths of optimal tours obtained by the well known TSP solver Concorde. In this paper we give a partial theoretical explanation of this correlation.
Classification : 41A55, 65D30, 65D32, 33C45
Keywords: traveling salesman problem, spectra of graphs, spectral radius, concorde TSP solver 
@article{BASS_2018_43_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 and Mirjana \v{C}angalovi\'c},
     title = {The traveling  salesman problem: {The} spectral radius and the length of an optimal tour},
     journal = {Bulletin de l'Acad\'emie serbe des sciences. Classe des sciences math\'ematiques et naturelles},
     pages = {18 },
     publisher = {mathdoc},
     volume = {43},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASS_2018_43_a2/}
}
TY  - JOUR
AU  - Dragoš Cvetković
AU  - Zorica Dražić
AU  - Vera Kovačević-Vujčić
AU  - Mirjana Čangalović
TI  - The traveling  salesman problem: The spectral radius and the length of an optimal tour
JO  - Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles
PY  - 2018
SP  - 18 
VL  - 43
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BASS_2018_43_a2/
LA  - en
ID  - BASS_2018_43_a2
ER  - 
%0 Journal Article
%A Dragoš Cvetković
%A Zorica Dražić
%A Vera Kovačević-Vujčić
%A Mirjana Čangalović
%T The traveling  salesman problem: The spectral radius and the length of an optimal tour
%J Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles
%D 2018
%P 18 
%V 43
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BASS_2018_43_a2/
%G en
%F BASS_2018_43_a2
Dragoš Cvetković; Zorica Dražić; Vera Kovačević-Vujčić; Mirjana Čangalović. The traveling  salesman problem: The spectral radius and the length of an optimal tour. Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 43 (2018), p. 18 . http://geodesic.mathdoc.fr/item/BASS_2018_43_a2/