GENERATING AND COUNTING HAMILTON CYCLES IN RANDOM REGULAR GRAPHS

Authors
FRIEZE A JERRUM M MOLLOY M ROBINSON R WORMALD N
Citation
A. Frieze et al., GENERATING AND COUNTING HAMILTON CYCLES IN RANDOM REGULAR GRAPHS, Journal of algorithms, 21(1), 1996, pp. 176-198
Citations number
15
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
21
Issue
1
Year of publication
1996
Pages
176 - 198
Database
ISI
SICI code
0196-6774(1996)21:1<176:GACHCI>2.0.ZU;2-F
Abstract
Let G be chosen uniformly at random from the set G(r, n) of r-regular graphs with vertex set [n]. We describe polynomial time algorithms tha t whp (i) find a Hamilton cycle in G, and (ii) approximately count the number of Hamilton cycles in G. (C) 1996 Academic Press, Inc.