# Questions tagged [hamiltonian-path]

Questions on Hamiltonian paths, that is, paths that visit each vertex exactly once in a graph.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
292 views

### How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
168 views

### Upper bound on the number of hamiltonian cycles on a $n \times n$ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n$ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
296 views

### Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
202 views

### Number of “hamiltonian tours” from upper left to lower left corner of a grid graph?

I got the following as an interview question: Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the ...
1k views

### Prove that a hamiltonian DAG has a single topological sort

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort". This is pretty much the idea of what I've come along: lets prove by ...
258 views

### Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.) The weights are constrained to be 0 and 1. I know ...
912 views

### Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

this is homework, so PLEASE do not give me the solution(!), but help me get there on my own. I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path ...
25 views

### Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?