The Traveling Salesman Problem in Bounded Degree Graphs

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)18
TidskriftACM Transactions on Algorithms
Volym8
Utgivningsnummer2
StatusPublished - 2012
PublikationskategoriForskning
Peer review utfördJa