Cloteaux, B.
and Valentin, L.
(2011),
Counting the Leaves of Trees, Congressus Numerantium, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=908869
(Accessed April 18, 2024)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Counting the Leaves of Trees
Published
Author(s)
, Luis A. Valentin
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
Pub Type
Journals
Download Paper
Keywords
randomized algorithm, combinatorial enumeration
Citation
Created December 19, 2011, Updated February 19, 2017