The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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.

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