Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
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.|
|Pages:||pp. 129 - 139|
|Keywords:||randomized algorithm, combinatorial enumeration|
|PDF version:||Click here to retrieve PDF version of paper (310KB)|