Counting the Number of Hamilton Cycles in Random Digraphs

DOI10.1002/RSA.3240030303MaRDI QIDQ4014635zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stephen Suen, Alan Frieze

Publication date 18 October 1992

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240030303

zbMATH Keywords

randomized algorithmsenumerationHamilton cyclesrandom digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Recommendations

• An algorithm for finding hamilton cycles in random directed graphs
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• On the number of hamilton cycles in a random graph
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs

Cites work

• An analysis of Monte Carlo algorithm for estimating the permanent

Cited in

(15)

• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• scientific article; zbMATH DE number 5239164 (Why is no real title available?)
• On the number of hamilton cycles in a random graph
• On the number of circuits in random graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Approximating the permanent: A simple approach
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• scientific article; zbMATH DE number 1047719 (Why is no real title available?)
• An analysis of Monte Carlo algorithm for estimating the permanent
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Approximately counting embeddings into random graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Algorithm for counting large directed loops
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Generating and Counting Hamilton Cycles in Random Regular Graphs

This page was built for publication: Counting the Number of Hamilton Cycles in Random Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4014635)