Stochastic Enumeration Method for Counting Trees

Vaisman, Radislav and Kroese, Dirk P (2015) Stochastic Enumeration Method for Counting Trees. Methodology and Computing in Applied Probability, . doi:10.1007/s11009-015-9457-4

Author Vaisman, Radislav
Kroese, Dirk P
Title Stochastic Enumeration Method for Counting Trees
Journal name Methodology and Computing in Applied Probability   Check publisher's open access policy
ISSN 1573-7713
Publication date 2015-08-16
Year available 2015
Sub-type Article (original research)
DOI 10.1007/s11009-015-9457-4
Open Access Status Not Open Access
Total pages 43
Place of publication New York, United States
Publisher Springer
Collection year 2016
Language eng
Formatted abstract
The problem of estimating the size of a backtrack tree is an important but hard problem in the computational sciences. An efficient solution of this problem can have a major impact on the hierarchy of complexity classes. The first randomized procedure, which repeatedly generates random paths through the tree, was introduced by Knuth. Unfortunately, as was noted by Knuth and a few other researchers, the estimator can introduce a large variance and become ineffective in the sense that it underestimates the cost of the tree. Recently, a new sequential algorithm called Stochastic Enumeration (SE) method was proposed by Rubinstein et al. The authors showed numerically that this simple algorithm can be very efficient for handling different counting problems, such as counting the number of satisfiability assignments and enumerating the number of perfect matchings in bipartite graphs. In this paper we introduce a rigorous analysis of SE and show that it results in significant variance reduction as compared to Knuth’s estimator. Moreover, we establish that for almost all random trees the SE algorithm is a fully polynomial time randomized approximation scheme (FPRAS) for the estimation of the overall tree size.
Keyword Randomized algorithms
Monte Carlo sampling
Multilevel splitting
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2016 Collection
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 01 Sep 2015, 00:22:19 EST by System User on behalf of Scholarly Communication and Digitisation Service