An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs

DOI10.1016/J.TCS.2010.10.014MaRDI QIDQ620956zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

Publication date 2 February 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.10.014

zbMATH Keywords

\#P-complete1-factorcountingHamiltonian cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1003265
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Counting the Number of Hamilton Cycles in Random Digraphs
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• An algorithm for finding hamilton cycles in random directed graphs

Cites work

• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Accelerating simulated annealing for the permanent and combinatorial counting problems
• An upper bound for permanents of nonnegative matrices
• Approximating the Permanent
• Approximating the permanent: A simple approach
• Exact sampling from perfect matchings of dense regular bipartite graphs
• Extending the minc-brègman upper bound for the permanent
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Graph theory with applications
• Hamilton Cycles in Random Regular Digraphs
• scientific article; zbMATH DE number 1003265 (Why is no real title available?)
• scientific article; zbMATH DE number 5764789 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• On the complexity of nonnegative-matrix scaling
• Random generation of combinatorial structures from a uniform distribution
• The complexity of computing the permanent

Cited in

(7)

• How many needles are in a haystack, or how to solve \#P-complete counting problems fast
• An efficient approximation algorithm for counting \(n\)-cycles in a graph
• scientific article; zbMATH DE number 1003265 (Why is no real title available?)
• Counting the Number of Hamilton Cycles in Random Digraphs
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings

This page was built for publication: An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs

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