Notices
Results 1 to 1 of 1

Thread: Complexity of Traveling Salesman Problem

  1. #1 Complexity of Traveling Salesman Problem 
    New Member
    Join Date
    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.


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •