Additive tree functionals with small toll functions and subtrees of random trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2012

Additive tree functionals with small toll functions and subtrees of random trees

Résumé

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.
Fichier principal
Vignette du fichier
dmAQ0106.pdf (296.25 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01197234 , version 1 (11-09-2015)

Identifiants

Citer

Stephan Wagner. Additive tree functionals with small toll functions and subtrees of random trees. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.67-80, ⟨10.46298/dmtcs.2984⟩. ⟨hal-01197234⟩

Collections

TDS-MACS
96 Consultations
661 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More