2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – joriki Sep 13 '11 at 8:02
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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