A number of important combinatorial counting problems can be reformulated into the problem of counting the number of leaf nodes on a tree. Since the basic leaf-counting problem is #P-complete, there is strong evidence that no polynomial time algorithm exists for this general problem. Thus, we propose a randomized approximation scheme for this problem, and then empirically compare its convergence rate with the classic method of Knuth. We then give an application of our scheme by introducing a new algorithm for estimating the number of bases of a matroid with an independence oracle.
Citation: Congressus Numerantium
Pub Type: Journals
randomized algorithm, combinatorial enumeration