Well-solvable special cases of the TSP : a survey

R.E. Burkhard, V.G. Deineko, J.A.A. Dal, van, G.J. Woeginger

Research output: Book/ReportReportAcademic

614 Downloads (Pure)


The Traveling Salesman Problem belongs to the most important and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently. We survey these special cases with emphasis on results obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler and Shmoys. Keywords: Traveling Salesman Problem, Combinatorial optimization, Polynomial time algorithm, Computational complexity.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages53
Publication statusPublished - 1996

Publication series

NameMemorandum COSOR
ISSN (Print)0926-4493


Dive into the research topics of 'Well-solvable special cases of the TSP : a survey'. Together they form a unique fingerprint.

Cite this