Stochastic enumeration method for counting NP-hard problems

DOI10.1007/s11009-011-9242-yzbMath1269.65012OpenAlexW2067049422MaRDI QIDQ352890

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

zbMATH Keywords

Markov chain Monte Carlo methodnumerical examplesself-avoiding walkssplittingsatisfiabilityone-step-look-ahead algorithmpolynomial time decision makingrare-eventsample search methodssequential importance sampling algorithmstochastic enumeration

Mathematics Subject Classification ID

Related Items (4)

Sequential Monte Carlo for counting vertex covers in general graphs ⋮ Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra ⋮ Stochastic enumeration with importance sampling ⋮ Stochastic enumeration method for counting trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• SampleSearch: importance sampling in presence of determinism
• The complexity of computing the permanent
• Sequential Monte Carlo for rare event estimation
• Efficient Monte Carlo simulation via the generalized splitting method
• The Gibbs cloner for combinatorial optimization, counting and sampling
• Random generation of combinatorial structures from a uniform distribution
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• Multilevel Splitting for Estimating Rare Event Probabilities
• Adaptive Multilevel Splitting for Rare Event Analysis
• Monte Carlo methods for the self-avoiding walk
• Approximating the permanent: A simple approach
• Equation of State Calculations by Fast Computing Machines
• 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
• Simulation and the Monte Carlo Method
• Probability and Computing
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Monte Carlo strategies in scientific computing
• Efficient implementation of the Pivot algorithm for self-avoiding walks

This page was built for publication: Stochastic enumeration method for counting NP-hard problems