Geodesic
Additive tree functionals with small toll functions and subtrees of random trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

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 divide-and-conquer 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. 
@article{DMTCS_2012_special_262_a5,
     author = {Wagner, Stephan},
     title = {Additive tree functionals with small toll functions and subtrees of random trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.2984},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2984/}
}
TY  - JOUR
AU  - Wagner, Stephan
TI  - Additive tree functionals with small toll functions and subtrees of random trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2984/
DO  - 10.46298/dmtcs.2984
LA  - en
ID  - DMTCS_2012_special_262_a5
ER  - 
%0 Journal Article
%A Wagner, Stephan
%T Additive tree functionals with small toll functions and subtrees of random trees
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2984/
%R 10.46298/dmtcs.2984
%G en
%F DMTCS_2012_special_262_a5
Wagner, Stephan. Additive tree functionals with small toll functions and subtrees of random trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.2984. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2984/

Cité par Sources :