Name
Abstract | ||
|---|---|---|
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]. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1137/S0036144596297514 | SIAM Review |
Keywords | Field | DocType |
combinatorial optimization,earlier survey,cal np,polynomial time,special case,well-solvable special cases,guided tour,hard problem,salesman problem,computational complexity,traveling salesman problem | Bottleneck traveling salesman problem,Mathematical optimization,Algorithm complexity,Combinatorial optimization,Travelling salesman problem,Time complexity,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
40 | 3 | 0036-1445 |
Citations | PageRank | References |
72 | 3.87 | 38 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rainer E. Burkard | 1 | 928 | 103.88 |
| Vladimir G. Deineko | 2 | 367 | 36.72 |
| René van Dal | 3 | 97 | 6.36 |
| Jack A. A. van der Veen | 4 | 213 | 14.61 |
| Jack A. A. van der Veen | 5 | 213 | 14.61 |
| Gerhard Woeginger | 6 | 4176 | 384.37 |