In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.
- A pyramidal tour
- Polynomially solvable classes
- The traveling salesman problem
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics