Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
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
Association for Computing Machinery (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
2016-04-01 10:25:09
date last changed
2022-02-25 01:31:45
@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}},
  keywords     = {{Counting; dynamic programming; inclusion-exclusion; permanent; Shearer's; entropy lemma; traveling salesman problem; trimming}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{18--18}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  series       = {{ACM Transactions on Algorithms}},
  title        = {{The Traveling Salesman Problem in Bounded Degree Graphs}},
  url          = {{http://dx.doi.org/10.1145/2151171.2151181}},
  doi          = {{10.1145/2151171.2151181}},
  volume       = {{8}},
  year         = {{2012}},
}