Counting the Number of Hamilton Cycles in Random Digraphs

DOI10.1002/RSA.3240030303zbMATH Open0771.05089DBLPjournals/rsa/FriezeS92OpenAlexW2101599991WikidataQ57401591 ScholiaQ57401591MaRDI QIDQ4014635FDOQ4014635

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

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

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)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• 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)