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)

8
checked on Sep 15, 2022

Google ScholarTM

Check

Altmetric

Altmetric


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