Special cases of the traveling salesman problem

摘要

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 research, the most general special cases are identified. The paper also contains a table of subclasses of the most general special cases. Applications and open questions are indicated.