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.
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. October1974. 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
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltoniancycleproblem are problems of determining whether a Hamiltonian path or a Hamiltoniancycle exists in a given graph (whether directed or undirected).
The Hamiltonian path problem for graph G is equivalent to the Hamiltoniancycleproblem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G.
The Hamiltoniancycleproblem 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.
Feeds |
Contact