Deǐneko, V. G.; van der Veen, J. A.; Rudolf, Rüdiger; Woeginger, Gerhard J. Three easy special cases of the Euclidean travelling salesman problem. (English) Zbl 0888.90141 RAIRO, Rech. Opér. 31, No. 4, 343-362 (1997). 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. Cited in 5 Documents MSC: 90C35 Programming involving graphs or networks 90C60 Abstract computational complexity for mathematical programming problems 90C27 Combinatorial optimization Keywords:distance matrix; travelling salesman problem; Demidenko conditions; Kalmanson conditions; Supnick conditions; polynomial time recognition algorithms PDFBibTeX XMLCite \textit{V. G. Deǐneko} et al., RAIRO, Rech. Opér. 31, No. 4, 343--362 (1997; Zbl 0888.90141) Full Text: DOI EuDML