## Generating and counting Hamilton cycles in random regular
graphs

**Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson and
Nicholas Wormald**
*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.*

Previous |

Index |

Next