The traveling salesman problem in bounded degree graphs
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto · ACM Transactions on Algorithms · 2012
We show that the traveling salesman problem in bounded-degree graphs can be solved in time O ((2-ϵ) n ), where ϵ > 0 depends only on the degree bound but not on the number of cities, n . The algorithm is a variant of the classical dynamic programming solution due to Bellman, and, independently, Held and Karp. In the case of bounded integer weights on the edges, we also give a polynomial-space algorithm with running time O ((2-ϵ) n ) on bounded-degree graphs. In addition, we present an analogous analysis of Ryser's algorithm for the permanent of matrices with a bounded number of nonzero entries in each column.