Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T10:55:24.656Z Has data issue: false hasContentIssue false
  • English
  • Français

The Travelling Salesman Problem in symmetric circulant matrices with two stripes

Published online by Cambridge University Press:  01 February 2008

IVAN GERACE and
FEDERICO GRECO
IVAN GERACE
Affiliation:
Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli 1, I-06123 Perugia, Italy Email: gerace@dipmat.unipg.it, greco@dipmat.unipg.it
FEDERICO GRECO
Affiliation:
Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli 1, I-06123 Perugia, Italy Email: gerace@dipmat.unipg.it, greco@dipmat.unipg.it
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 18 , Special Issue 1: in memory of Sauro Tulipani , February 2008, pp. 165 - 175
Copyright
Copyright © Cambridge University Press2008

References

Bogdanowicz, Z. (2005) Hamiltonian Circuits in Sparse Circulant Digraphs. Ars Combinatoria 76 213–223.Google Scholar
Burkard, R. E. and Sandholzer, W. (1991) Efficiently solvable special cases of the bottleneck traveling salesman problem. Discrete Applied Mathematics 32 61–76.CrossRefGoogle Scholar
Codenotti, B., Gerace, I. and Vigna, S. (1998) Hardness Results and Spectral Techniques for Combinatorial Problems on Circulant Graphs. Linear Algebra and its Application 285 123–142.CrossRefGoogle Scholar
Davis, P. J. (1979) Circulant Matrices, John Wiley and Sons.Google Scholar
Garfinkel, R. S. (1977) Minimizing wallpaper waste, part 1: a class of traveling salesman problems. Oper. Res. 25 741–751.CrossRefGoogle Scholar
Gerace, I. and Greco, F. (2006) Bounds for the Symmetric Circulant Traveling Salesman Problem. Rapporto Tecnico del Dip. di Matematica e Informatica dell'Università di Perugia, Italy, TR 4-2006.Google Scholar
Gerace, I. and Irving, R. W. (1998) The traveling salesman problem in circulant graphs. Technical Report of Department of Computing Science, University of Glasgow, U.K., TR-1998-15.Google Scholar
Heuberger, C. (2002) On Hamiltonian Toeplitz graphs. Discrete Mathematics 245 107–125.CrossRefGoogle Scholar
Muzychuk, M. (2004) A solution of the isomorphism problem for circulant graphs. Proc. of the London Math. Society 88 (3)1–41.CrossRefGoogle Scholar
Van Der Veen, J. A. A. (1992) Solvable Cases of the Traveling Salesman Problem with Various Objective Functions, Ph.D. Thesis, University of Groningen, Holland.Google Scholar
Yang, Q. F., Burkard, R. E., Çela, E. and Wöginger, G. J. (1997) Hamiltonian cycles in circulant digraphs with two stripes. Discrete Mathematics 176 233–254.CrossRefGoogle Scholar