Advanced

The Traveling Salesman Problem in Bounded Degree Graphs

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2012) In ACM Transactions on Algorithms 8(2). p.18-18
Abstract
We show that the traveling salesman problem in bounded-degree graphs can be solved in time O((2 - epsilon)(n)), where epsilon > 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 - epsilon)(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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Counting, dynamic programming, inclusion-exclusion, permanent, Shearer's, entropy lemma, traveling salesman problem, trimming
in
ACM Transactions on Algorithms
volume
8
issue
2
pages
18 - 18
publisher
ACM
external identifiers
  • wos:000304065800010
  • scopus:84860270503
ISSN
1549-6333
DOI
10.1145/2151171.2151181
language
English
LU publication?
yes
id
5c8d7532-170b-4576-ad7e-4f60e1a2a469 (old id 2813087)
date added to LUP
2012-06-25 07:30:26
date last changed
2017-08-27 03:24:42
@article{5c8d7532-170b-4576-ad7e-4f60e1a2a469,
  abstract     = {We show that the traveling salesman problem in bounded-degree graphs can be solved in time O((2 - epsilon)(n)), where epsilon > 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 - epsilon)(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.},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  issn         = {1549-6333},
  keyword      = {Counting,dynamic programming,inclusion-exclusion,permanent,Shearer's,entropy lemma,traveling salesman problem,trimming},
  language     = {eng},
  number       = {2},
  pages        = {18--18},
  publisher    = {ACM},
  series       = {ACM Transactions on Algorithms},
  title        = {The Traveling Salesman Problem in Bounded Degree Graphs},
  url          = {http://dx.doi.org/10.1145/2151171.2151181},
  volume       = {8},
  year         = {2012},
}