WELL-SOLVABLE SPECIAL CASES OF THE TRAVELING SALESMAN PROBLEM - A SURVEY

The traveling salesman problem (TSP) belongs to the most basic, most i mportant, and most investigated problems in combinatorial optimization . Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey NP these special case s with emphasis on the results that have been obtained during the deca de 1985-1995. This survey complements an earlier survey from 1985 comp iled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-1 43].