Hamiltonian path problem
|
|
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. The problem of finding a Hamiltonian cycle or path is in FNP.
There is a simple relation between the two problems. The Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G.
The Hamiltonian cycle problem is a special case of the traveling salesman problem, obtained by setting the distance between two cities to unity if they are adjacent and infinity otherwise.
The directed and undirected Hamiltonian cycle problems were two of Karp's 21 NP-complete problems. Garey and Johnson showed shortly afterwards in 1974 that the directed Hamiltonian cycle problem remains NP-complete for planar graphs and the undirected Hamiltonian cycle problem remains NP-complete for cubic graphs.
| Contents |
Quadratic algorithm for Dirac (dense) graphs
If the degree of every vertex is greater or equal than v/2, then the problem can be resolved in quadratic time. See [1] (http://cgm.cs.mcgill.ca/~perouz/cs251/documents/solutions6/solutions6.html) for details.
See also
External links
- Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations (http://www.densis.fee.unicamp.br/~moscato/Hamilton.html)
- Proof that the Hamiltonian Cycle problem is NP-complete by reduction from 3-SAT (http://cs482.elliottback.com/archives/2005/03/28/lecture-25-hamiltonian-cycle-problem/)
References
- Rubin, Frank, "A Search Procedure for Hamilton Paths and Circuits' (http://portal.acm.org/citation.cfm?doid=321850.321854)". Journal of the ACM, Volume 21, Issue 4. October 1974. ISSN 0004-5411
- Nasu, Michiro, "A Study of Hamiltonian Circuit Problem (http://www.geocities.com/babalabo/Hamilton/Draft.html)". fourth draft, April 4, 1996 - August 18, 1999
- M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems (http://portal.acm.org/citation.cfm?id=803884). Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63. 1974.de:Hamiltonkreisproblem