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.
Previous | Index | Next An error occured whilst processing this directive