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 language | English |
---|---|
Pages (from-to) | 176-198 |
Number of pages | 23 |
Journal | Journal of Algorithms |
Volume | 21 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1996 |
Externally published | Yes |