All Questions
Tagged with traveling-salesman-problem graph-theory
15 questions
4
votes
2
answers
418
views
What Kind of Graph is This?
I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.
The overarching rationale is that the reduction is done via a sequence of ...
- 13.2k
3
votes
2
answers
1k
views
Is there a lower bound for the computational complexity of the traveling salesman problem?
A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did ...
- 6,290
3
votes
0
answers
145
views
Hamiltonian cycle polytope for the hypercube graph
Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...
- 393
2
votes
1
answer
133
views
Constructing optimal Hamilton cycles from optimal Hamilton paths
Question:
can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging ...
- 13.2k
2
votes
1
answer
139
views
Description of Linear Time Algorithm for TSP in Halin Graphs
I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
- 13.2k
2
votes
0
answers
119
views
Corporate salesman problem
A salesman is employed by a large corporation. He has a $n$ cities to visit, connected by roads, forming a graph. But as travel takes a lot of time, he has to pick hotels between visits. He cannot ...
- 1,626
1
vote
1
answer
173
views
Could you provide some TSP examples from real world to test a new algorithm?
It's well known that to find a hamilton cycle is NPC, while TSP is NPH.
But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
- 175
1
vote
0
answers
61
views
A generalized/set hamiltonian cycle problem on directed graphs
So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
- 111
0
votes
0
answers
99
views
Reformulate Traveling Salesman Problem in areas traversed problem
I was wondering whether one has ever considered to reformulate TSP in terms of the areas traversed in either direction. Thus take three initial points of the solution they span a triangle with a ...
- 1
0
votes
0
answers
185
views
Adapting Held–Karp algorithm to visit groups of vertices
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 ...
- 101
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
0
votes
0
answers
64
views
Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs
Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...
- 13.2k
0
votes
0
answers
77
views
Travelling salesman problem with variable weights
Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...
- 79
0
votes
0
answers
59
views
A variant of travel salesman problem with charging points
Given a graph composed of a set $V$ of nodes, each representing a point to be visited by a salesman, and a set of fixed charging points. The salesman disposes a car that can travel $D$ distance before ...
- 367
-1
votes
1
answer
243
views
Helsgaun's $k$-Opt moves
In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP
heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as:
with a cycle defined here:
which ...
- 13.2k