The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

The travelling salesman problem in bounded degree graphs

På svenska

Author

  • Andreas Björklund
  • Thore Husfeldt
  • Petteri Kaski
  • Mikko Koivisto

Summary, in English

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.

Publishing year

2008

Language

English

Pages

198-209

Publication/Series

Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science

Volume

5125

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

35th International Colloquium on Automata, Languages and Programming

Conference date

2008-07-07 - 2008-07-11

Conference place

Reykjavik, Iceland

Status

Published

Project

  • Exact algorithms

Research group

  • Algorithms

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-540-70574-1