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.68388MaRDI 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

counting; 1-factor; Hamiltonian cycle; \#P-complete

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

68W20: Randomized algorithms

05C45: Eulerian and Hamiltonian graphs

05C42: Density (toughness, etc.)

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