Sökning: onr:"swepub:oai:lup.lub.lu.se:ac36d2e9-b39f-48d1-a5ea-27bb82aff7dc" >
The travelling sale...
The travelling salesman problem in bounded degree graphs
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
Kaski, Petteri (författare)
-
visa fler...
-
Koivisto, Mikko (författare)
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2008
- 2008
- Engelska.
-
Ingår i: Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540705741 ; 5125, s. 198-209
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas