3 EASY SPECIAL CASES OF THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

It is known that iii case the distance matrix in the Travelling Salesm an Problem (TSP) fulfills cer?ain combinatorial conditions (e.g. the D emidenko conditions, the Kalmanson conditions or the Supnick condition s) then the TSP is solvable in polynomial time. This paper deals with the problem of recognizing Euclidean instances of the TSP for which th ere is a renumbering of the cities such that the corresponding renumbe red distance matrix fulfills the Demidenko (Kalmanson,Supnick) conditi ons. We provide polynomial time recognition algorithms for all three c ases.