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

DOI10.1016/j.tcs.2010.10.014zbMath1209.68388OpenAlexW2163114902MaRDI QIDQ620956

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

counting1-factorHamiltonian cycle\#P-complete

Mathematics Subject Classification ID

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

Related Items

Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• On the complexity of nonnegative-matrix scaling
• An upper bound for permanents of nonnegative matrices
• Exact sampling from perfect matchings of dense regular bipartite graphs
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Accelerating simulated annealing for the permanent and combinatorial counting problems
• Approximating the permanent: A simple approach
• Hamilton Cycles in Random Regular Digraphs
• Extending the minc-brègman upper bound for the permanent
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents