The Symmetric Circulant Traveling Salesman Problem asks for the minimum cost of a Hamiltonian cycle in a circulant weighted undirected graph. The computational complexity of this problem is not known. Just a constructive upper bound, and a good lower bound have been determined. This paper provides a characterization of the two stripe case. Instances where the minimum cost of a Hamiltonian cycle is equal either to the upper bound, or to the lower bound are recognized. A new construction providing Hamiltonian cycles, whose cost is in many cases lower than the upper bound, is proposed for the remaining instances.
The Traveling salesman problem in circulant weighted graphs with two stripes
GRECO, FEDERICO;GERACE, Ivan
2007
Abstract
The Symmetric Circulant Traveling Salesman Problem asks for the minimum cost of a Hamiltonian cycle in a circulant weighted undirected graph. The computational complexity of this problem is not known. Just a constructive upper bound, and a good lower bound have been determined. This paper provides a characterization of the two stripe case. Instances where the minimum cost of a Hamiltonian cycle is equal either to the upper bound, or to the lower bound are recognized. A new construction providing Hamiltonian cycles, whose cost is in many cases lower than the upper bound, is proposed for the remaining instances.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
