2. This paper (pg. 14) gives an algorithm for finding the optimal Hamiltonian path, although it's a little tough to decipher.
What little of if I can decipher indicates that you have to pick a node 'p' as the final node, and then apply the algorithm. But what if I picked a bad 'p'? So that then means that I need to do the algorithm V-1 times to make sure that I picked the best 'p' or find a better 'p'.
So given lines 3-4 already show this:
for s = 1 to N-2 for i,j = 1 to N
This looks like O(n3) to me. Doing another loop to try out all the possible p's would bring this algorithm up to O(n4). Am I missing something?
Still beats O(n!), though.
This post has been edited by Skydiver: 27 August 2012 - 11:30 AM