A NEW CLASS OF PYRAMIDALLY SOLVABLE SYMMETRICAL TRAVELING SALESMAN PROBLEMS

An instance of the symmetric traveling salesman problem (STSP) is pyramidally solvable if there is a shortest tour that is pyramidal. A pyramidal tour is a Hamiltonian tour that consists of two parts; according to the labeling of the vertices in the first part the vertices are visited in increasing order and in the second part in decreasing order. It is well known that a shortest pyramidal tour can be found in O(n(2)) time. In this paper it is,shown that the STSP restricted to the class of distance matrices [GRAPHICS] is pyramidally solvable. Furthermore, it is shown that D-NEW not subset of D-DEMI, i.e., that D-NEW is not contained in the class of symmetric Demidenko matrices D-DEMI that was, until now, the most general class of pyramidally solvable STSPs. It is also shown that D-DEMI not subset of D-NEW.