Mei Xue

"Finding Hamilton Cycles in Cubic Graphs"

Abstract:

This thesis explores randomized algorithms for finding Hamilton cycles in cubic graphs.

After giving some basic definitions, we discuss an algorithm for generating random 3-regular graphs. This is used for testing. Then two approaches for finding Hamilton cycles in random cubic graphs are presented, a random permutation method and a Markov chain method. Finally, we compare the preformance of these two approaches and describe a backtracking algorithm for checking the hamiltonicicy of a graph. The latter can be applied to graphs of modest size for which the randomized algorithms can not find a Hamilton cycle.