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 travelling salesman problem in bounded degree graphs

Författare:
Publiceringsår: 2008
Språk: Engelska
Sidor: 198-209
Publikation/Tidskrift/Serie: Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science
Volym: 5125
Dokumenttyp: Konferensbidrag
Förlag: Springer

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering

Övriga

35th International Colloquium on Automata, Languages and Programming
2008-07-07/2008-07-11
Reykjavik, Iceland
  • VR
Published
  • Exact algorithms
Yes
  • Algorithms
  • ISSN: 0302-9743
  • ISBN: 978-3-540-70574-1

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