×

Three easy special cases of the Euclidean travelling salesman problem. (English) Zbl 0888.90141

Summary: It is known that in case the distance matrix in the travelling salesman problem (TSP) fulfills certain combinatorial conditions (e.g. the Demidenko conditions, the Kalmanson conditions or the Supnick conditions) then the TSP is solvable in polynomial time. This paper deals with the problem of recognizing Euclidean instances of the TSP for which there is a renumbering of the cities such that the corresponding renumbered distance matrix fulfills the Demidenko (Kalmanson, Supnick) conditions. We provide polynomial time recognition algorithms for all three cases.

MSC:

90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI EuDML