Well-solvable special cases of the Traveling Salesman Problem : a survey

R.E. Burkard, V.G. Deineko, R. Dal, van, J.A.A. Veen, van der, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

133 Citaten (Scopus)
619 Downloads (Pure)


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].
Originele taal-2Engels
Pagina's (van-tot)496-546
TijdschriftSIAM Review
Nummer van het tijdschrift3
StatusGepubliceerd - 1998


Duik in de onderzoeksthema's van 'Well-solvable special cases of the Traveling Salesman Problem : a survey'. Samen vormen ze een unieke vingerafdruk.

Citeer dit