An asymmetric analogue of van der Veen conditions and the traveling salesman problem Original Research Article

In (J.A.A. van der Veen, SIAM J. Discrete Math, 7, 1994, 585–592), van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions) a shortest pyramidal tour is optimal. From this fact, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analogue of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones.