Novel characteristics of split trees by use of renewal theory

DOI10.1214/EJP.v17-1723zbMath1244.05058arXiv1005.4594MaRDI QIDQ428606

Cecilia Holmgren

Publication date: 22 June 2012

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

renewal theory; random trees; split trees

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

68P10: Searching and sorting

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

60C05: Combinatorial probability

68P05: Data structures

Related Items

Embedding small digraphs and permutations in binary trees and split trees, The fluctuations of the giant cluster for percolation on random split trees, Random Recursive Trees and Preferential Attachment Trees are Random Split Trees, Inversions in Split Trees and Conditional Galton–Watson Trees, Tree limits and limits of random trees, The asymptotic distribution of cluster sizes for supercritical percolation on random split trees, The total path length of split trees, Renewal theory in the analysis of tries and strings, Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey, The \(k\)-cut model in deterministic and random trees, Embedding small digraphs and permutations in binary trees and split trees, \(k\)-cut on paths and some trees