Stochastic enumeration method for counting NP-hard problems
DOI10.1007/S11009-011-9242-YzbMATH Open1269.65012OpenAlexW2067049422MaRDI QIDQ352890FDOQ352890
Authors: Reuven Y. Rubinstein 
Publication date: 5 July 2013
Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11009-011-9242-y
Recommendations
- Stochastic enumeration method for counting trees
- Stochastic enumeration with importance sampling
- How many needles are in a haystack, or how to solve \#P-complete counting problems fast
- Monte-Carlo approximation algorithms for enumeration problems
- An analysis of Monte Carlo algorithms for counting problems
numerical examplesMarkov chain Monte Carlo methodsatisfiabilitysplittingone-step-look-ahead algorithmpolynomial time decision makingrare-eventsample search methodsself-avoiding walkssequential importance sampling algorithmstochastic enumeration
Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Combinatorial probability (60C05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Monte Carlo strategies in scientific computing
- Equation of state calculations by fast computing machines
- Simulation and the Monte Carlo Method
- The complexity of computing the permanent
- Random generation of combinatorial structures from a uniform distribution
- Multilevel splitting for estimating rare event probabilities
- Adaptive Multilevel Splitting for Rare Event Analysis
- Sequential Monte Carlo for rare event estimation
- Title not available (Why is that?)
- Probability and Computing
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- The Gibbs cloner for combinatorial optimization, counting and sampling
- Efficient implementation of the Pivot algorithm for self-avoiding walks
- Efficient Monte Carlo simulation via the generalized splitting method
- The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
- Genetic genealogical models in rare event analysis
- Monte Carlo methods for the self-avoiding walk
- An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
- Approximating the permanent: A simple approach
- RARE EVENT SIMULATION
- Estimating the Number of s-t Paths in a Graph
- A Two-Step Branching Splitting Model Under Cost Constraint for Rare Event Analysis
- SampleSearch: importance sampling in presence of determinism
- Theory and Applications of Satisfiability Testing
Cited In (8)
- Approximate verification and enumeration problems
- Monte-Carlo approximation algorithms for enumeration problems
- Sequential Monte Carlo for counting vertex covers in general graphs
- Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
- How many needles are in a haystack, or how to solve \#P-complete counting problems fast
- Stochastic enumeration with importance sampling
- Model counting of monotone conjunctive normal form formulas with spectra
- Stochastic enumeration method for counting trees
This page was built for publication: Stochastic enumeration method for counting NP-hard problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352890)
