Hamiltonian problem
<computability> (Or "Hamilton's problem") A problem in graph theory posed
by William Hamilton: given a graph, is there a path through the graph which
visits each vertex precisely once (a "Hamiltonian path")? Is there a Hamiltonian
path which ends up where it started (a "Hamiltonian cycle" or "Hamiltonian
tour")?
Hamilton's problem is NP-complete. It has numerous applications, sometimes
completely unexpected, in computing.
Home.
(1997-07-18)
Nearby terms:
Hamilton « Hamiltonian cycle « Hamiltonian path «
Hamiltonian problem » Hamiltonian tour » Hamilton's
problem » hammer
