Open AccessComplexity indices for the traveling salesman problem continued
Author(s) -
Dragoš Cvetković,
Zorica Dražić,
Vera Kovačevíc-Vujčić
Publication year - 2021
Publication title -
yugoslav journal of operations research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.221
H-Index - 21
eISSN - 1820-743X
pISSN - 0354-0243
DOI - 10.2298/yjor201121014c
Subject(s) - travelling salesman problem , combinatorics , solver , mathematics , sequence (biology) , computational complexity theory , integer (computer science) , enhanced data rates for gsm evolution , discrete mathematics , computer science , mathematical optimization , algorithm , artificial intelligence , genetics , biology , programming language
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 subgraphs 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.