Approximately Counting Hamilton Cycles in Dense Graphs

Martin Dyer and Alan Frieze and Mark Jerrum

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.

LFCS report ECS-LFCS-93-259, April 1993.

Previous | Index | Next