The Traveling Salesman Problem in Bounded Degree Graphs
Author
Summary, in English
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.
Department/s
Publishing year
2012
Language
English
Pages
18-18
Publication/Series
ACM Transactions on Algorithms
Volume
8
Issue
2
Document type
Journal article
Publisher
Association for Computing Machinery (ACM)
Topic
- Computer Science
Keywords
- Counting
- dynamic programming
- inclusion-exclusion
- permanent
- Shearer's
- entropy lemma
- traveling salesman problem
- trimming
Status
Published
ISBN/ISSN/Other
- ISSN: 1549-6333