The travelling salesman problem in bounded degree graphs

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

We show that the travelling salesman problem in bounded-degree graphs can be solved in tune 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 present a polynomial-space algorithm with running tune O((2 - epsilon)(n)) on bounded-degree graphs.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationAutomata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science
FörlagSpringer
Sidor198-209
Volym5125
ISBN (tryckt)978-3-540-70574-1
StatusPublished - 2008
PublikationskategoriForskning
Peer review utfördJa
Evenemang35th International Colloquium on Automata, Languages and Programming - Reykjavik, Island
Varaktighet: 2008 jul 72008 jul 11

Publikationsserier

Namn
Volym5125
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens35th International Colloquium on Automata, Languages and Programming
LandIsland
OrtReykjavik
Period2008/07/072008/07/11