Talk:Hamiltonian path problem
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
 | This  level-5 vital article is rated C-class on Wikipedia's content assessment scale.It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
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)
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.