The travelling salesman problem in bounded degree graphs

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.

• Författare: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Avdelning/ar: Institutionen för datavetenskap; Computer Science; Parallella System
• 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
• Länkar: http://dx.doi.org/10.1007/978-3-540-70575-8_17
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: 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
• Projekt: Exact algorithms
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-540-70574-1