[prev] 98 [next]

Hamiltonian Path and Circuit (cont)

Analysis: worst case requires (V-1)! paths to be examined

Consider a graph with isolated vertex and the rest fully-connected

[Diagram:Pic/hamilton-worst.png]

Checking hasHamiltonianPath(g,x,0) for any x

  • requires us to consider every possible path
  • e.g 1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-2-3, …
  • starting from any x, there are 3! paths ⇒ 4! total paths
  • there is no path of length 5 in these (V-1)! possibilities
There is no known simpler algorithm for this task ⇒ NP-hard.

Note, however, that the above case could be solved in constant time if
we had a fast check for 0 and x being in the same connected component