0

Suppose you have $4$ cities $1, 2, 3$ and $4$. You want to find all ways to go from $1$ to $4$ such as $1=4$, $1=2-2=4$, $1=3-3=4$, $1=3-3=2-2=4$ and $1=2-2=3-3=4$. Distances between cities do not matter. What is the name of this TSP variant where I need to only find the possible routes (not requiring to connect all vertices but need to connect starting-point and end-point)?

Mhenni Benghorbal
  • 47,431
hhh
  • 5,469
  • Since distances don't matter, you are simply listing all permutations of all subsets of the remaining $n-2$ vertices. I'm not aware of a standard name for this: it might just lie in the neutral zone between "not long enough to require a name" and "not elegant enough to deserve one", so I'd go with Tomas's suggestion. – Erick Wong Jul 27 '13 at 17:06

2 Answers2

1

You are looking for the set of paths between two vertices of a simple, unweighted graph. This has little to do with the TSP and I don't think there is a name for it, any preciser than I stated it.

Some kind of depth-first search might solve this, you may want to look on this question on Mathoverflow, where the matter already has been discussed.

Community
  • 1
Tomas
  • 4,534
  • There must be more specific name to this, not just "set of paths between two vertices of a simple, unweighted graph". If uncareful, it is pretty easy to create $n!$ algorithm where $n$ is the amount of vertices. I am trying to find out whether a specific programming language such as Matlab has something ready done for this kind of problems. Finding the precise mathematical name would help googling. – hhh Aug 02 '13 at 11:20
  • I disagree, that there must be a name. There are names for interesting problems, not for all problems. In graph theory, usually it is important to check, if there is a path or what the shortest path is or what the path of least weight is, maybe even the number of distinct paths. Computing the whole set of paths does not seem so interesting, that it would get a name or be integrated in any software and certainly not in matlab. – Tomas Aug 02 '13 at 14:35
  • 1
    Also, note, that there are exactly $\sum_{i=1}^{n-2}\frac{(n-2)!}{i!}$ many paths on a complete graph with $n$ vertices. So you are bound to have a "$n!$ algorithm" in the general case no matter how careful you are. Read the link to the Mathoverflow-question I posted for a discussion on the efficiency of such algorithms. – Tomas Aug 02 '13 at 14:40
  • Yes that is correct but you probably meant $\sum_{k=0}^{n} \frac{n!}{k!}$ amount of arrangements, A000522. I clearly need to stop going through the paths in some point, thank you for repeating that! So the $O((np+1)(m+n))$ algorithm does not traverse all paths?! I haven't yet understood it, it is faster because it cuts traversing in some point "stuck"?! – hhh Aug 02 '13 at 14:48
  • I did not read this discussion carefully, the poster claims, it does traverse all paths. However, this is not a contradiction to $\mathcal O(n!)$-time, since it involves the number if paths $p$, which is generally in the size of $\mathcal O(n!)$. So this algorithm is not better than $\mathcal O(n!)$ in general, but guaranteed to behave better on sparse graphs. Also, I think my sum is right, since start and end vertex are fixed. – Tomas Aug 02 '13 at 15:39
0

I want to draw more attention to this finding...

You want to find all ways to go from 1 to 4 such as 1=4, 1=2−2=4, 1=3−3=4, 1=3−3=2−2=4 and 1=2−2=3−3=4.

There is an exact solution for it, check up the integer sequence A000522 for the total number of arrangements of a set with $n$ elements.

hhh
  • 5,469