The Travelling Salesman Problem in Bounded Degree Graphs

We show that the travelling salesman problem in bounded-degreegraphs can be solved in time $O\bigl((2-\epsilon)^n\bigr)$, whereε 0 depends only on the degree bound but noton the number of cities, n. The algorithm is a variant ofthe classical dynamic programming solution due to Bellman, and,independently, Held and Karp. In the case of bounded integerweights on the edges, we also present a polynomial-space algorithmwith running time $O\bigl((2-\epsilon)^n\bigr)$ on bounded-degreegraphs.