The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Vandegriend's Finding Hamiltonian Cycles

From his abstract:

My Master's thesis "Finding Hamiltonian Cycles: Algorithms, Graphs and Performance" deals with the Hamiltonian cycle problem, an NP-C problem in graph theory. The problem consists of finding a tour (or cycle) that visits all the vertices once and returns to the starting vertex. I have investigated several related issues:

* Design issues for backtrack Hamiltonian cycle algorithms * Design issues for heuristic Hamiltonian cycle algorithms * Generalizations of the knight's tour problem (a subset of the Hamiltonian cycle problem). * Hard regions of the Hamiltonian cycle problem. My goal here is to identify graphs and graph properties that make the Hamiltonian cycle problem hard or that distinguish between various Hamiltonian cycle algorithms. I have focused mainly on low degree randomized graphs.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Hamiltonian Cycle (9)

    This page last modified on 2008-07-10 .