|
|
|
|
|
Hamiltonian Path ProblemIn 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. 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. 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 http://cgm.cs.mcgill.ca/~perouz/cs251/documents/solutions6/solutions6.html for details. See also External links References
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|