Large deviations for the weighted height of an extended class of trees

DOI10.1007/S00453-006-0112-XMaRDI QIDQ866962zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Luc Devroye

Publication date 14 February 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-006-0112-x

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Large deviations of the height of a random tree
• Large deviations for random trees
• On weighted heights of random trees
• scientific article; zbMATH DE number 1087333
• scientific article; zbMATH DE number 953136
• Asymptotics of heights in random trees constructed by aggregation
• Large deviations for the leaves in some random trees
• scientific article; zbMATH DE number 515653

Cited in

(27)

• Heavy subtrees of Galton-Watson trees with an application to Apollonian networks
• On weighted depths in random binary search trees
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Correction terms for the height of weighted recursive trees
• Minima in branching random walks
• Long and short paths in uniform random recursive dags
• Martingales and large deviations for binary search trees
• On tail bounds for random recursive trees
• Limit theorems for depths and distances in weighted random b-ary recursive trees
• It's a small world for random surfers
• An Analysis of the Height of Tries with Random Weights on the Edges
• Large deviations for the leaves in some random trees
• Large deviations of the height of a random tree
• Some properties of random Apollonian networks
• SMALL-WORLD EFFECT IN GEOGRAPHICAL ATTACHMENT NETWORKS
• Random recursive trees and preferential attachment trees are random split trees
• The height of random k‐trees and related branching processes
• On longest paths and diameter in random Apollonian networks
• Note on the weighted internal path length of \(b\)-ary trees
• Building random trees from blocks
• On martingale tail sums for the path length in random trees
• Depths in random recursive metric spaces
• Analysis of the rate functions of large deviations for symbol statistics
• The total path length of split trees
• Large deviation properties for pattern statistics in primitive rational models
• Weighted height of random trees
• A functional limit theorem for the profile of \(b\)-ary trees

This page was built for publication: Large deviations for the weighted height of an extended class of trees

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