Generating and Counting Hamilton Cycles in Random Regular Graphs

DOI10.1006/jagm.1996.0042zbMath0857.68084WikidataQ57401561 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 algorithms; Hamilton cycles

Mathematics Subject Classification ID

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

68W10: Parallel algorithms in computer science

Related Items

The dominating number of a random cubic graph, Hamilton cycles in the union of random permutations, Unnamed Item, Approximately Counting Embeddings into Random Graphs, Heavy and light paths and Hamilton cycles, 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, A threshold result for loose Hamiltonicity in random regular uniform hypergraphs, 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