Stephan Wagner

Additive tree functionals with small toll functions and subtrees of random trees
dmtcs:2984 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

https://doi.org/10.46298/dmtcs.2984
Additive tree functionals with small toll functions and subtrees of random treesArticle
Authors: Stephan Wagner ^{1}
NULL
Stephan Wagner
1 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
Many parameters of trees are additive in the sense that they can be computed recursively from the sum of the branches plus a certain toll function. For instance, such parameters occur very frequently in the analysis of divideandconquer algorithms. Here we are interested in the situation that the toll function is small (the average over all trees of a given size $n$ decreases exponentially with $n$). We prove a general central limit theorem for random labelled trees and apply it to a number of examples. The main motivation is the study of the number of subtrees in a random labelled tree, but it also applies to classical instances such as the number of leaves.
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: additive tree functional,small toll function,number of subtrees,size of subtrees,random trees,[INFO.INFODS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFODM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATHCO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFOCG] Computer Science [cs]/Computational Geometry [cs.CG]