Hamiltonian path problem - Definition and Overview

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determinining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. 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.

See also

• Traveling salesman problem

External links

• Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations (http://www.densis.fee.unicamp.br/~moscato/Hamilton.html)

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