Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/1510| Title: | The traveling salesman problem: the spectral radius and the length of | Authors: | Dražić, Zorica Cvetković, Dragoš Vujčić, Kovačević Vera Čangalović, Mirjana |
Affiliations: | Numerical Mathematics and Optimization | Keywords: | Traveling salesman problem;spectra of graphs;spectral radius;Concorde TSP solver | Issue Date: | 2018 | Rank: | M51 | Publisher: | Beograd : Srpska akdemija nauka i umetnosti | Journal: | Bulletin Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques | Abstract: | 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 |
URI: | https://research.matf.bg.ac.rs/handle/123456789/1510 |
| Appears in Collections: | Research outputs |
Show full item record
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.