Generating and Counting Hamilton Cycles in Random Regular Graphs

DOI10.1006/jagm.1996.0042zbMath0857.68084OpenAlexW1991965073WikidataQ57401561 ScholiaQ57401561MaRDI QIDQ4895803

Robert W. Robinson, Michael S. O. Molloy, Alan M. Frieze, Nicholas C. Wormald, Mark R. Jerrum

Publication date: 16 December 1996

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1807/9464

zbMATH Keywords

polynomial time algorithmsHamilton cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (16)

3-star factors in random \(d\)-regular graphs ⋮ An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three ⋮ The number of Euler tours of random directed graphs ⋮ The dominating number of a random cubic graph ⋮ An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs ⋮ Cycle Factors and Renewal Theory ⋮ Heavy and light paths and Hamilton cycles ⋮ Hamiltonian decompositions of random bipartite regular graphs. ⋮ A threshold result for loose Hamiltonicity in random regular uniform hypergraphs ⋮ Hamilton cycles containing randomly selected edges in random regular graphs ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ Hamilton cycles in the union of random permutations ⋮ Unnamed Item ⋮ Approximately Counting Embeddings into Random Graphs ⋮ THE ASYMPTOTIC DISTRIBUTION OF THE NUMBER OF 3-STAR FACTORS IN RANDOM d-REGULAR GRAPHS ⋮ Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs

This page was built for publication: Generating and Counting Hamilton Cycles in Random Regular Graphs