Stochastic enumeration method for counting trees

DOI10.1007/s11009-015-9457-4zbMath1358.05059OpenAlexW2118668105WikidataQ118141917 ScholiaQ118141917MaRDI QIDQ518856

Radislav Vaisman, Dirk P. Kroese

Publication date: 30 March 2017

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11009-015-9457-4

zbMATH Keywords

Monte Carlo samplingrandomized algorithmsmultilevel splitting

Mathematics Subject Classification ID

Trees (05C05) Monte Carlo methods (65C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Random walks on graphs (05C81)

Related Items (4)

Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ State space splitting of a finite markov process and some discussions on related counting processes ⋮ Without-replacement sampling for particle methods on finite state spaces ⋮ Stochastic enumeration with importance sampling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stochastic enumeration method for counting NP-hard problems
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• 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
• Problems and theorems in analysis. I. Series, integral calculus, theory of functions. Transl. from the German by Dorothee Aeppli
• Estimating the number of vertices of a polyhedron
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• On Counting Independent Sets in Sparse Graphs
• Approximate counting by dynamic programming
• The Complexity of Enumeration and Reliability Problems
• Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
• Estimating the Efficiency of Backtrack Programs
• Tree Size by Partial Backtracking
• Approximately counting cliques
• The Splitting Method for Decision Making
• Probability Inequalities for Sums of Bounded Random Variables
• FPTAS for Counting Monotone CNF
• Simulation and the Monte Carlo Method
• Some limit theorems for the total progeny of a branching process
• Sequential Monte Carlo Methods for Statistical Analysis of Tables

This page was built for publication: Stochastic enumeration method for counting trees