A NEW CLASS OF PYRAMIDALLY SOLVABLE SYMMETRICAL TRAVELING SALESMAN PROBLEMS

An instance of the symmetric traveling salesman problem (STSP) is pyra midally solvable if there is a shortest tour that is pyramidal. A pyra midal tour is a Hamiltonian tour that consists of two parts; according to the labeling of the vertices in the first part the vertices are vi sited 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 clas s 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 wa s, until now, the most general class of pyramidally solvable STSPs. It is also shown that D-DEMI not subset of D-NEW.