Generating and Counting Hamilton Cycles in Random Regular Graphs

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

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

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 algorithms; Hamilton cycles

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

Related Items

Unnamed Item, The dominating number of a random cubic graph, Approximately Counting Embeddings into Random Graphs, The number of Euler tours of random directed graphs, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, 3-star factors in random \(d\)-regular graphs, Hamiltonian decompositions of random bipartite regular graphs., Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, Hamilton cycles containing randomly selected edges in random regular graphs, Cycle Factors and Renewal Theory, THE ASYMPTOTIC DISTRIBUTION OF THE NUMBER OF 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