Asymptotic cost of cutting down random free trees

MaRDI QIDQ4906619zbMATH OpenFDO

Authors Elahe Zohoorian Azad

Publication date 28 February 2013

Full work available at URL https://arxiv.org/abs/1008.3049

zbMATH Keywords

additive functionals on treesCayley treesHadamard product of generating functionslimit lawmethod of momentsrecurrence

Mathematics Subject Classification ID

Combinatorial probability (60C05) Local time and additive functionals (60J55) Searching and sorting (68P10) Combinatorics in computer science (68R05)

Abstract: The limit distribution of the total cost incurred by splitting a tree uniformly distributed on the set of all finite free trees, appears as an additive functional induced by a toll equal to the square of the size of tree. The main tools used are the recent results connecting the asymptotics of generating functions with the asymptotics of their Hadamard product, and the method of moments.

Recommendations

• Cost functionals for large random trees
• Cost functionals for large (uniform and simply generated) random trees
• Limit Laws for the Optimal Directed Tree with Random Costs
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• Asymptotical growth of a class of random trees
• scientific article; zbMATH DE number 3965074
• scientific article; zbMATH DE number 1506504
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• On a tail bound for analyzing random trees
• Asymptotics of the number of forests consisting of unrooted trees

Cited in

(2)

• Cost functionals for large (uniform and simply generated) random trees
• Cost functionals for large random trees

This page was built for publication: Asymptotic cost of cutting down random free trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4906619)