The Travelling Salesman Problem in symmetric circulant matrices with two stripes

Autor:	Ivan Gerace, Federico Greco
Rok vydání:	2008
Předmět:	Circulant Graphs TSP Computational Complexity Discrete mathematics Computational complexity theory Lin–Kernighan heuristic Upper and lower bounds Travelling salesman problem Computer Science Applications Combinatorics Mathematics (miscellaneous) Circulant matrix Mathematics
Zdroj:	Mathematical Structures in Computer Science. 18:165-175
ISSN:	1469-8072 0960-1295
DOI:	10.1017/s0960129508006609
Popis:	The Symmetric Circulant Travelling Salesman Problem asks for the minimum cost tour in a symmetric circulant matrix. The computational complexity of this problem is not known – only upper and lower bounds have been determined. This paper provides a characterisation of the two-stripe case. Instances where the minimum cost of a tour is equal to either the upper or lower bound are recognised. A new construction providing a tour is proposed for the remaining instances, and this leads to a new upper bound that is closer than the previous one.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e0f06e00bf617b7b94cd09e97018579a https://doi.org/10.1017/s0960129508006609 Zobrazit plný text záznamu