Finding Hamilton cycles in cubic graphs
MetadataShow full item record
This thesis explores randomized algorithms for _nding Hamilton cycles in cubic graphs.|After giving some basic de_nitions, we discuss an algorithm for generating random 3-regular graphs. This is used for testing. Then two approaches for _nding Hamilton cycles in random cubic graphs are presented, a random permutation method and a Markov chain method. Finally, we compare the performance of these two approaches and describe a backtracking algorithm for checking the hamil- tonicity of a graph. The latter can be applied to graphs of modest size for which the randomized algorithms can not _nd a Hamilton cycle.