Finding Hamilton cycles in cubic digraphs and restricted Cayley digraphs

This thesis explores randomized algorithms for finding Hamilton cycles in cubic digraphs and in diregular Cayley digraphs of degree 2 in which one generator is an involution. For random cubic digraphs two approaches for finding Hamilton cycles are discussed a random permutation method and a Markov chain method. The special properties of restricted Cayley digraphs which are relevant to finding Hamilton cycles in them are explored. Then, three algorithms are presented for finding Hamilton cycles in restricted Cayley digraphs. Results of testing the algorithms on random cubic graphs and restricted Cayley digraphs of moderate size (1000 2000 vertices) are reported.