An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
DOI10.1016/J.TCS.2010.10.014zbMATH Open1209.68388OpenAlexW2163114902MaRDI QIDQ620956FDOQ620956
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
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
Directed graphs (digraphs), tournaments (05C20) 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) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- The complexity of computing the permanent
- Random generation of combinatorial structures from a uniform distribution
- Title not available (Why is that?)
- Title not available (Why is that?)
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- Approximating the Permanent
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating the permanent: A simple approach
- Generating and Counting Hamilton Cycles in Random Regular Graphs
- On the complexity of nonnegative-matrix scaling
- An upper bound for permanents of nonnegative matrices
- Extending the minc-brègman upper bound for the permanent
- Exact sampling from perfect matchings of dense regular bipartite graphs
- Title not available (Why is that?)
- Accelerating simulated annealing for the permanent and combinatorial counting problems
- Hamilton Cycles in Random Regular Digraphs
Cited In (4)
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- How many needles are in a haystack, or how to solve \#P-complete counting problems fast
- Counting the Number of Hamilton Cycles in Random Digraphs
- An efficient approximation algorithm for counting \(n\)-cycles in a graph
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)
