Generating and Counting Hamilton Cycles in Random Regular Graphs

Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

30 Citations (Scopus)

Abstract

Let G be chosen uniformly at random from the set G script sign(r, n) of mr-regular graphs with vertex set [n]. We describe polynomial time algorithms that whp (i) find a Hamilton cycle in G, and (ii) approximately count the number of Hamilton cycles in G.

Original languageEnglish
Pages (from-to)176-198
Number of pages23
JournalJournal of Algorithms
Volume21
Issue number1
DOIs
Publication statusPublished - 1996
Externally publishedYes

Cite this