<p>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. </p>

CC BY-SA 3.0
2013-03-16T10:07:40.447Z
Not sure what protocol is on stackexchange regarding unanswered questions, but I am still very interested in the answer!
smartyfish
CC BY-SA 3.0
2013-03-16T13:14:45.960Z
Perhaps a related notion is the ASP-completeness (Another Solution Problem completeness) formalized by [Takayuki Yato](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.6324&rep=rep1&type=pdf): 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.
Marzio De Biasi
<graph-theory><tsp>
N shortest tours in a graph
smartyfish
# N shortest tours in a graph

(Asked by: username_0 on 2013-03-14)

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.

**Tags:** graph-theory, tsp
> **Comments:**
> **username_0**: Not sure what protocol is on stackexchange regarding unanswered questions, but I am still very interested in the answer!  
> **username_1**: Perhaps a related notion is the ASP-completeness (Another Solution Problem completeness) formalized by [Takayuki Yato](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.6324&rep=rep1&type=pdf): 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.  

---

## 0 answers

