Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog all special cases of polynomial time solvable TSP with sufficient detail to categorize characteristics of those specific exceptions.

It would seem that many specific cases probably involve some sort of geometric configuration. It would be interesting to know if there are situations where one could find an algebra of approaches that could be used to solve more and more complicated paths. I didn't know if this idea could be better defined.

share|cite|improve this question
Although that paper uses the same terminology, I think it would be better to speak of something like specific subclasses of TSP solvable in polynomial time -- "special cases" sounds to me as if it refers to problem instances, and of course the concept of polynomial time can't be applied to individual problem instances. – joriki Sep 13 '11 at 8:02

First place I would look is the (nearly 600-page) book, The Traveling Salesman Problem, by Applegate, Bixby, Chvatal, and Cook.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.