Abstract: We describe a fully polynomial randomized approximation scheme for the problem of determining the number of Hamiltonian cycles in an n-vertex graph with minimum degree (1/2 + epsilon)n, for any fixed epsilon > 0. We also show that the exact counting problem is #P-complete.
This file contains a slightly shortened version of the technical report of April 1993.
Previous | Index | Next An error occured whilst processing this directive