An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
From MaRDI portal
Publication:620956
DOI10.1016/j.tcs.2010.10.014zbMath1209.68388MaRDI QIDQ620956
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
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
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