The paper surveys special cases of the traveling salesman problem that
are in the literature. The tables include polynomial time recognition
algorithms and relationships among special cases. As a result of rese
arch, the most general special cases are identified. The paper also co
ntains a table of subclasses of the most general special cases. Applic
ations and open questions are indicated.