Unknown
Reputation: 53
TSP for Complete Directed Graph
Does there exist a polynomial time algorithm for Travelling Salesman Problem on complete directed graph?
Upvotes: 4
Views: 1712
Answers (1)
wrwrwr
Reputation: 1066
Unlikely. If there was one you could take any graph and add all the missing edges with a very high weight. That would allow solving the standard version of the problem, which is known to be NP-hard.
Upvotes: 3
Related Questions
- Travelling Salesman Problem
- Traveling Salesman Problem with additional partial ordering
- TSP Where Vertices Can be Visited Multiple Times
- Traveling Salesman (TSP) no return
- Traveling salesman on a directed graph with extra nods
- a variation of TSP : limit time, visit as many nodes as possible
- Exact euclidean Travelling Salesman
- TSP and Lin-Kernighan algorithm from primm graph
- python tsp travelling salesman undirected graph
- Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED