Results 1 to 2 of 2

Thread: Complexity of Traveling Salesman Problem

  1. #1 Complexity of Traveling Salesman Problem 
    New Member
    Join Date
    May 2008

    I posted this question to the Computer Science forum, but the focus there seems to be more on software and systems. Perhaps Mathematics is a more appropriate place for algorithms/theoretical computer science topics. If you think there is a better forum for this post, please let me know. And now for my question...

    Can the Traveling Salesman Problem (TSP) be solved in sub-exponential time when restricted to graphs with bounded treewidth? Arnborg and Proskurowski (1989, citation below) gave a linear-time algorithm for Hamiltonian Circuit on graphs with bounded treewidth. Can this be extended to TSP?



    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  


  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    According to the almighty

    Quote Originally Posted by Wikipedia
    An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight. It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.
    In other words, yeah, a result for Hamiltonian circuits should also apply to TSP.

    Reply With Quote  

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