I'm searching for papers dealing with the problem of finding not just the shortest tour in the graph (TSP) but finding N shortest tours. Somewhat surprisingly, I didn't find any mention of it, anywhere. I might be searching under a wrong name.

  • $\begingroup$ Not sure what protocol is on stackexchange regarding unanswered questions, but I am still very interested in the answer! $\endgroup$
    – smartyfish
    Mar 16, 2013 at 10:07
  • $\begingroup$ Perhaps a related notion is the ASP-completeness (Another Solution Problem completeness) formalized by Takayuki Yato: for a given instance $x$ of and a solution $s$ to it, find a solution to $x$ other than $s$. In particular in its paper it is proved that Hamiltonian cycle problem on grid graphs with deg < 4 is ASP-complete, since TSP is a generalization, it should be ASP-complete, too. $\endgroup$ Mar 16, 2013 at 13:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.