NIST logo

Publication Citation: Counting the Leaves of Trees

NIST Authors in Bold

Author(s): Brian D. Cloteaux; Luis A. Valentin;
Title: Counting the Leaves of Trees
Published: December 19, 2011
Abstract: 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
Volume: 207
Pages: pp. 129 - 139
Keywords: randomized algorithm; combinatorial enumeration
Research Areas: Math
PDF version: PDF Document Click here to retrieve PDF version of paper (310KB)