The travelling salesman problem in bounded degree graphs
(2008) 35th International Colloquium on Automata, Languages and Programming 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:
https://lup.lub.lu.se/record/1406127
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko
- organization
- publishing date
- 2008
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 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
- conference location
- Reykjavik, Iceland
- conference dates
- 2008-07-07 - 2008-07-11
- 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
- 2016-04-01 12:05:18
- date last changed
- 2025-01-02 05:16:30
@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}},
doi = {{10.1007/978-3-540-70575-8_17}},
volume = {{5125}},
year = {{2008}},
}