The Science Forum - Scientific Discussion and Debate  
 
 Live Chat    FAQ    Search    Usergroups
 
Register  ::  Log in Log in to check your private messages
 
Science Forum Forum Index » Computer Science » Complexity of Traveling Salesman Problem

  
 Complexity of Traveling Salesman Problem « View previous topic :: View next topic » 
Author Message
diogenes
Posted: Fri May 30, 2008 1:27 pm    Post subject: Complexity of Traveling Salesman Problem Reply with quote

Forum Freshman
Forum Freshman

Joined: 30 May 2008
Posts: 3
Hello,

Does anyone know the complexity of the Traveling Salesman Problem (TSP) on graphs of bounded treewidth? Arnborg and Proskurowski (1989, citation below) gave a linear-time algorithm for Hamiltonian circuits on graphs with bounded treewidth. Can this be extended to TSP?

Thanks!


Reference:

Stefan Arnborg and Andrzej Proskurowski. Linear Time Algorithms for NP-Hard Problems Restricted to Partial k-trees. Discrete Applied Mathematics 23, pp. 11-24. 1989.
Back to top
View user's profile Send private message
Display posts from previous:   
   Page 1 of 1

Science Forum Forum Index » Computer Science » Complexity of Traveling Salesman Problem
Jump to:  



You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
 
 


Google
 

© 2004-2008 Thescienceforum.com

Sponsored by EnluxLED

Partner Forums
Politics Forum  Radar Detector