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.

  • 0
    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.2011-09-13

1 Answers 1

2

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