Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap
irt.Org

Hamiltonian problem

You are here: irt.org | FOLDOC | 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.

(http://ing.unlp.edu.ar/cetad/mos/Hamilton.html).

(1997-07-18)

Nearby terms: Hamilton « Hamiltonian cycle « Hamiltonian path « Hamiltonian problem » Hamiltonian tour » Hamilton's problem » hammer

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL

©2018 Martin Webb