Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
From MaRDI portal
Publication:2061784
DOI10.1007/978-3-030-76657-3_2zbMath1484.68057OpenAlexW3160283760MaRDI QIDQ2061784
Publication date: 21 December 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-76657-3_2
heightrenewal theorysizebond percolationcontraction methodlimit lawsrandom treesbinary search treecuttingsQuicksortinversionsdepthssorting algorithmstotal path lengthsplit trees
Central limit and other weak theorems (60F05) Trees (05C05) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Applications of branching processes (60J85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Data structures (68P05) Renewal theory (60K05)
Cites Work
- Novel characteristics of split trees by use of renewal theory
- Dynamics of the evolving Bolthausen-Sznitman coalescent
- Cutting down trees with a Markov chainsaw
- The total path length of split trees
- Random recursive trees and the Bolthausen-Sznitman coalescent
- Large deviations for the weighted height of an extended class of trees
- Weighted height of random trees
- Applications of the theory of records in the study of random trees
- On the analysis of stochastic divide and conquer algorithms
- The \(k\)-cut model in deterministic and random trees
- Supercritical percolation on large scale-free random trees
- Cutting resilient networks -- complete binary trees
- Embedding small digraphs and permutations in binary trees and split trees
- \(k\)-cut on paths and some trees
- On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees
- Yule processes with rare mutation and their applications to percolation on \(b\)-ary trees
- Almost Giant Clusters for Percolation on Large Trees with Logarithmic Heights
- On the normality of giant components
- Sizes of the largest clusters for supercritical percolation on random recursive trees
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Random Records and Cuttings in Binary Search Trees
- Emergence of Scaling in Random Networks
- Asymptotic normality of the size of the giant component in a random hypergraph
- Percolation
- Random cutting and records in deterministic and random trees
- Random Trees
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- On the height of random m‐ary search trees
- A note on the height of binary search trees
- Universal Limit Laws for Depths in Random Trees
- Percolation
- On the internal path length ofd-dimensional quad trees
- Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
- Inversions in Split Trees and Conditional Galton–Watson Trees
- Cutting down random trees
- Percolation on random recursive trees
- A limit theorem for “quicksort”
- Quicksort
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
