Talk:Hamiltonian path problem

Unclear wording

In the Randomized Algorithm section, I do not understand this phrase: "pick a neighbor uniformly at random, and rotate using that neighbor as a pivot". It isn't clear at all what this might mean. Can anyone expand on this? If so, thanks! CosineKitty (talk) 19:50, 12 April 2008 (UTC)

Second that. PAStheLoD (talk) 08:51, 29 October 2008

Thirded. JasonHise (talk) 10:54, 5 April 2009 (UTC) (UTC)

OK, I think I know what he meant by that, so I added a clarifying sentence. But now I have another question. Is it possible for this algorithm to get "stuck" such that no possible sequence of random choices can lead to a solution? I think it is. Certainly if the graph has bottlenecks it seems possible. So which graphs pose this danger and which don't? --Jorend (talk) 15:40, 23 April 2009 (UTC)

Why should the algorithm be fast, or even find a hamiltonian path? It is certainly possible to get stuck in a number of ways, for instance in a graph whose only edges belong to an hamiltonian path. The section should be rewritten or removed. --80.13.108.224 (talk) 03:00, 31 January 2011 (UTC)

After a bit research I rewrote the section: a "rotation" takes place in the notation (a subpath "abcde" is replaced by "edcba"), and "rotation-extension" is part of many classical algorithms, but is not a whole algorithm for finding hamiltonian paths. --80.13.108.224 (talk) 12:03, 2 February 2011 (UTC)

Examples

Can someone give examples where one encounters the Hamiltonian path problem in practice? --Abdull (talk) 10:17, 22 July 2008 (UTC)

Added an applications section Soup222 (talk) 17:41, 9 October 2023 (UTC)

Implementations

Can someone add some references to implementations which are practically good? M.jooyandeh (talk) 03:23, 14 May 2012 (UTC)

Added an applications section Soup222 (talk) 17:42, 9 October 2023 (UTC)

Reductions

I think it would be helpful to add other reductions such as a reduction from 3-SAT to Hampath Soup222 (talk) 17:40, 9 October 2023 (UTC)