Technical Reports

The ICICS/CS Reading Room

UBC CS TR-81-08 Summary

Solvable Cases of the Travelling Salesman Problem, September 1981 Paul C. Gilmore

This paper is a chapter in a book on the travelling salesman problem edited by Eugene L. Lawler, Jan Karel Lenstra and Alexander H.G. Rinooy Kan. By a solvable case of the travelling salesman problem is meant a case of the distance matrix for which a polynomial algorithm exists. In this paper several previously known special cases are related and extended. Further, an upper bound is obtained on the cost of an optimal tour for a broad class of matrices.

If you have any questions or comments regarding this page please send mail to