The Travelling Salesman Problem in Bounded Degree Graphs

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Abstract

We show that the travelling salesman problem in bounded-degree graphs can be solved in time $O\bigl((2-\epsilon)^n\bigr)$ , 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 present a polynomial-space algorithm with running time $O\bigl((2-\epsilon)^n\bigr)$ on bounded-degree graphs.
BibTeX
@inproceedings{bjorklund2008travelling,
  author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
  title = {{The Travelling Salesman Problem in Bounded Degree Graphs}},
  booktitle = {ICALP},
  year = {2008},
  doi = {10.1007/978-3-540-70575-8\_17},
}

Loading related content...

Figure