Skip to main content
U.S. flag

An official website of the United States government

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)

Brian D. Cloteaux, 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

Keywords

randomized algorithm, combinatorial enumeration

Citation

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 March 3, 2024)
Created December 19, 2011, Updated February 19, 2017