Authors: Cvetković, Dragoš
Dražić, Zorica
Kovačević-Vujčić, Vera
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: COMPLEXITY INDICES for the TRAVELING SALESMAN PROBLEM CONTINUED
Journal: Yugoslav Journal of Operations Research
Volume: 31
Issue: 4
First page: 471
Last page: 481
Issue Date: 1-Jan-2021
Rank: M24
ISSN: 0354-0243
DOI: 10.2298/YJOR201121014C
Abstract: 
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.
Keywords: Complexity index | Concorde TSP Solver | Correlation | Random instances | Traveling salesman problem
Publisher: Faculty of Organizational Sciences, Belgrade

Show full item record

Page view(s)

10
checked on Jan 31, 2023

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.