Cost functionals for large random trees
From MaRDI portal
Publication:4632476
zbMATH Open1411.68032arXiv1605.04245MaRDI QIDQ4632476FDOQ4632476
Authors: Jean-François Delmas, Jean-Stéphane Dhersin, Marion Sciauveau 
Publication date: 29 April 2019
Abstract: Additive tree functionals allow to represent the cost of many divide-and-conquer algorithms. We give an invariance principle for such tree functionals for the Catalan model (random tree uniformly distributed among the full binary ordered trees with given number of internal nodes) and for simply generated trees (including random tree uniformly distributed among the ordered trees with given number of nodes). In the Catalan model, this relies on the natural embedding of binary trees into the Brownian excursion and then on elementary second moment computations. We recover results first given by Fill and Kapur (2004) and then by Fill and Janson (2009). In the simply generated case, this relies on the convergence of conditioned Galton-Watson towards stable L'evy trees. We recover results first given by Janson (2003 and 2016) in the quadratic case and give a generalization to the stable case.
Full work available at URL: https://arxiv.org/abs/1605.04245
Recommendations
- Cost functionals for large (uniform and simply generated) random trees
- Limiting distributions for additive functionals on Catalan trees
- Additive tree functionals with small toll functions and subtrees of random trees
- Asymptotic cost of cutting down random free trees
- Search trees: metric aspects and strong limit theorems
Cited In (2)
This page was built for publication: Cost functionals for large random trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632476)
