The Traveling Salesman Problem in Bounded Degree Graphs
(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:
https://lup.lub.lu.se/record/2813087
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko
- organization
- publishing date
- 2012
- 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}}, }