• People
• Events
• Research

Generating and counting Hamilton cycles in random regular graphs

Abstract: Polynomial-time, randomised algorithms are developed for the problems of constructing, sampling uniformly at random, and approximately counting Hamiltonian cycles in a random k-regular, n-vertex graph. The algorithms are based on the simulation of a rapidly mixing Markov chain, and succeed with probability tending to 1, as n tends to infinity. The key to quantifying the performance of the algorithms is the ``analysis of variance'' method.

LFCS report ECS-LFCS-94-313, December 1994.