Advanced

The travelling salesman problem in bounded degree graphs

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2008) 35th International Colloquium on Automata, Languages and Programming In Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science 5125. p.198-209
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science
volume
5125
pages
198 - 209
publisher
Springer
conference name
35th International Colloquium on Automata, Languages and Programming
external identifiers
  • wos:000258073400017
  • scopus:49049114076
ISSN
0302-9743
1611-3349
ISBN
978-3-540-70574-1
DOI
10.1007/978-3-540-70575-8_17
project
Exact algorithms
language
English
LU publication?
yes
id
ac36d2e9-b39f-48d1-a5ea-27bb82aff7dc (old id 1406127)
date added to LUP
2009-06-08 14:03:55
date last changed
2017-08-27 04:03:16
@inproceedings{ac36d2e9-b39f-48d1-a5ea-27bb82aff7dc,
  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.},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  booktitle    = {Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science},
  isbn         = {978-3-540-70574-1},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {198--209},
  publisher    = {Springer},
  title        = {The travelling salesman problem in bounded degree graphs},
  url          = {http://dx.doi.org/10.1007/978-3-540-70575-8_17},
  volume       = {5125},
  year         = {2008},
}