The Travelling Salesman Problem in Bounded Degree Graphs
Lists
Only you see this
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...