Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

The Traveling Salesman Problem in Bounded Degree Graphs

Författare:
Publiceringsår: 2012
Språk: Engelska
Sidor:
Publikation/Tidskrift/Serie: ACM Transactions on Algorithms
Volym: 8
Nummer: 2
Dokumenttyp: Artikel
Förlag: Association for Computing Machinery

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • Counting
  • dynamic programming
  • inclusion-exclusion
  • permanent
  • Shearer's
  • entropy lemma
  • traveling salesman problem
  • trimming

Övriga

Published
Yes
  • ISSN: 1549-6325

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen