DAIS - Digital Archive of the Serbian Academy of Sciences and Arts
    • English
    • Српски
    • Српски (Serbia)
  • English 
    • English
    • Serbian (Cyrillic)
    • Serbian (Latin)
  • Login
View Item 
  •   DAIS
  • Cрпска академија наука и уметности / Serbian Academy of Sciences and Arts
  • Bulletin
  • Classe des sciences mathematiques et naturelles
  • View Item
  •   DAIS
  • Cрпска академија наука и уметности / Serbian Academy of Sciences and Arts
  • Bulletin
  • Classe des sciences mathematiques et naturelles
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The traveling salesman problem: The spectral radius and the length of an optimal tour

Thumbnail
2018
(1).pdf (256.1Kb)
Authors
Cvetković, Dragoš
Dražić, Zorica
Kovačević-Vujčić, Vera
Čangalović, Mirjana
Conference object (Published version)
Metadata
Show full item record
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.
Keywords:
Traveling salesman problem / Spectra of graphs / Spectral radius / Concorde TSP solver
Source:
Bulletin T.CLI de l’Académie serbe des sciences et des arts, 2018, 17-26
Publisher:
  • Beograd : Académie Serbe des sciences et des arts
Funding / projects:
  • Mathematical Modelas and Optimization Methods on Large-Scale Systems (RS-174010)
  • Graph theory and mathematical programming with applications in chemistry and computer science (RS-174033)
  • Serbian Academy of Sciences and Arts, Project F-159
Note:
  • Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles. Sciences mathématiques. . - 43 , 151 (2018)

ISSN: 0561-7332

[ Google Scholar ]
Handle
https://hdl.handle.net/21.15107/rcub_dais_9081
URI
https://dais.sanu.ac.rs/123456789/9081
Collections
  • Classe des sciences mathematiques et naturelles
Institution/Community
Cрпска академија наука и уметности / Serbian Academy of Sciences and Arts
TY  - CONF
AU  - Cvetković, Dragoš
AU  - Dražić, Zorica
AU  - Kovačević-Vujčić, Vera
AU  - Čangalović, Mirjana
PY  - 2018
UR  - https://dais.sanu.ac.rs/123456789/9081
AB  - 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.
PB  - Beograd : Académie Serbe des sciences et des arts
C3  - Bulletin T.CLI de l’Académie serbe des sciences et des arts
T1  - The traveling salesman problem: The spectral radius and the length of an optimal tour
SP  - 17
EP  - 26
UR  - https://hdl.handle.net/21.15107/rcub_dais_9081
ER  - 
@conference{
author = "Cvetković, Dragoš and Dražić, Zorica and Kovačević-Vujčić, Vera and Čangalović, Mirjana",
year = "2018",
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.",
publisher = "Beograd : Académie Serbe des sciences et des arts",
journal = "Bulletin T.CLI de l’Académie serbe des sciences et des arts",
title = "The traveling salesman problem: The spectral radius and the length of an optimal tour",
pages = "17-26",
url = "https://hdl.handle.net/21.15107/rcub_dais_9081"
}
Cvetković, D., Dražić, Z., Kovačević-Vujčić, V.,& Čangalović, M.. (2018). The traveling salesman problem: The spectral radius and the length of an optimal tour. in Bulletin T.CLI de l’Académie serbe des sciences et des arts
Beograd : Académie Serbe des sciences et des arts., 17-26.
https://hdl.handle.net/21.15107/rcub_dais_9081
Cvetković D, Dražić Z, Kovačević-Vujčić V, Čangalović M. The traveling salesman problem: The spectral radius and the length of an optimal tour. in Bulletin T.CLI de l’Académie serbe des sciences et des arts. 2018;:17-26.
https://hdl.handle.net/21.15107/rcub_dais_9081 .
Cvetković, Dragoš, Dražić, Zorica, Kovačević-Vujčić, Vera, Čangalović, Mirjana, "The traveling salesman problem: The spectral radius and the length of an optimal tour" in Bulletin T.CLI de l’Académie serbe des sciences et des arts (2018):17-26,
https://hdl.handle.net/21.15107/rcub_dais_9081 .

DSpace software copyright © 2002-2015  DuraSpace
About DAIS - Digital Archive of the Serbian Academy of Sciences and Arts | Send Feedback

CoreTrustSealre3dataOpenAIRERCUB
 

 

All of DSpaceInstitutions/communitiesAuthorsTitlesSubjectsThis institutionAuthorsTitlesSubjects

Statistics

View Usage Statistics

DSpace software copyright © 2002-2015  DuraSpace
About DAIS - Digital Archive of the Serbian Academy of Sciences and Arts | Send Feedback

CoreTrustSealre3dataOpenAIRERCUB