  In the path version of the Travelling Salesman Problem (Path-TSP), a salesman
is looking for the shortest Hamiltonian path through a set of n cities. The
salesman has to start his journey at a given city s, visit every city exactly
once, and finally end his trip at another given city t. In this paper we
identify a new polynomially solvable case of the Path-TSP where the distance
matrix of the cities is a so-called Demidenko matrix. We identify a number of
crucial combinatorial properties of the optimal solution, and we design a
dynamic program with time complexity $O(n^6)$.
