THE HIDDEN ALGORITHM OF ORES THEOREM ON HAMILTONIAN CYCLES

Authors
PALMER EM
Citation
Em. Palmer, THE HIDDEN ALGORITHM OF ORES THEOREM ON HAMILTONIAN CYCLES, Computers & mathematics with applications, 34(11), 1997, pp. 113-119
Citations number
12
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
34
Issue
11
Year of publication
1997
Pages
113 - 119
Database
ISI
SICI code
0898-1221(1997)34:11<113:THAOOT>2.0.ZU;2-Z
Abstract
In 1960, Ore found a simple sufficient condition for a graph to have a Hamiltonian cycle. We expose a heuristic algorithm, hidden in Ore's p roof, which can be very effective in actually finding such a cycle. Th is algorithm is always reasonably efficient and suggests an easy proof that almost all graphs are Hamiltonian.