The Traveling Salesman Problem in Bounded Degree Graphs

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.

• Författare: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2012
• Språk: Engelska
• Sidor: 18-18
• Publikation/Tidskrift/Serie: ACM Transactions on Algorithms
• Volym: 8
• Issue: 2
• Länkar: http://dx.doi.org/10.1145/2151171.2151181
• Dokumenttyp: Artikel i tidskrift
• Förlag: Association for Computing Machinery (ACM)
• Ämne: Computer Science
• Nyckelord: Counting; dynamic programming; inclusion-exclusion; permanent; Shearer's; entropy lemma; traveling salesman problem; trimming
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 1549-6333