TY - JOUR
T1 - Well-solvable special cases of the Traveling Salesman Problem : a survey
AU - Burkard, R.E.
AU - Deineko, V.G.
AU - Dal, van, R.
AU - Veen, van der, J.A.A.
AU - Woeginger, G.J.
PY - 1998
Y1 - 1998
N2 - The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an ${\cal NP}$-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985--1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem---A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87--143].
AB - The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an ${\cal NP}$-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985--1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem---A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87--143].
U2 - 10.1137/S0036144596297514
DO - 10.1137/S0036144596297514
M3 - Article
SN - 0036-1445
VL - 40
SP - 496
EP - 546
JO - SIAM Review
JF - SIAM Review
IS - 3
ER -