0
$\begingroup$

The Held–Karp algorithm has exponential time complexity $\Theta\left(2^n n^2\right)$, which is better than brute forcing the TSP which requires $\Theta(n !)$.

I'm interesting in amending the Held–Karp algorithm to determine the shortest path between each group of vertices. This is different from the TSP as it allows vertices to be travelled twice and not every vertix needs to be visited. Imagine, instead of visiting each city, visiting each country that each city is in.

I have an algorithm to brute force the solution, but this is very slow. Is it possible to adapt the Held–Karp algorithm to finding the shortest path between groups?

enter image description here

For example, in this weighted graph, here vertices 1 - 3 are in the red group, 4-6 in blue , 7-9 in green, and 10-12 is in purple. The shortest route is 4 <-> 10 <-> 3 <-> 7.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ you can check the 1989 paper by JOHN R. CURRENT and DAVID A. SCHILLING: "Covering Traveling Salesman" jstor.org/stable/25768381 Not sure if your problem is different; would be interesting to know in which respect. $\endgroup$
    – Manfred Weis
    Commented Jul 19, 2023 at 15:23
  • $\begingroup$ This is the solution. I feel stupid for not finding this. Thank you! $\endgroup$
    – Tomi
    Commented Jul 19, 2023 at 15:29
  • $\begingroup$ There is no need to feel stupid; similar things happen(ed) to me, but it had the positive effect that I found solutions myself, occasionally better ones. $\endgroup$
    – Manfred Weis
    Commented Jul 19, 2023 at 15:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .