A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

DOI10.1002/RSA.20233zbMATH Open1187.05068OpenAlexW4240348261MaRDI QIDQ3633016FDOQ3633016

Alexander Iksanov, Martin Möhle, Michael Drmota, Uwe Rösler

Publication date: 16 June 2009

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20233

Recommendations

• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• Random cutting and records in deterministic and random trees
• Isolating nodes in recursive trees
• Multiple isolation of nodes in recursive trees
• Isolating the most recent entry in a random recursive tree by random cuts

zbMATH Keywords

singularity analysisrecursive treestable limiting law

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• On the analysis of stochastic divide and conquer algorithms
• Cutting down recursive trees
• Title not available (Why is that?)
• Random cutting and records in deterministic and random trees
• Cutting down very simple trees
• Title not available (Why is that?)
• On the contraction method with degenerate limit equation.
• The Bernoulli sieve
• Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• Destruction of very simple trees
• Title not available (Why is that?)

Cited In (34)

• Weak limits for the largest subpopulations in Yule processes with high mutation probabilities
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• The total path length of split trees
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• On the number of allelic types for samples taken from exchangeable coalescents with mutation
• Asymptotic results for coalescent processes without proper frequencies and applications to the two-parameter Poisson-Dirichlet coalescent
• Total internal and external lengths of the Bolthausen-Sznitman coalescent
• Title not available (Why is that?)
• Inverting the cut-tree transform
• Inversions in Split Trees and Conditional Galton–Watson Trees
• Isolating the most recent entry in a random recursive tree by random cuts
• Random records and cuttings in binary search trees
• Percolation on random recursive trees
• On Asymptotics of the Beta Coalescents
• Stochastic analysis of the extra clustering model for animal grouping
• Asymptotic hitting probabilities for the Bolthausen-Sznitman coalescent
• Λ-coalescents: a survey
• On the number of collisions in beta(\(2, b\))-coalescents
• Cutting down trees with a Markov chainsaw
• On Λ-Coalescents with Dust Component
• The \(k\)-cut model in deterministic and random trees
• The fluctuations of the giant cluster for percolation on random split trees
• Fires on large recursive trees
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• Asymptotic cost of cutting down random free trees
• Cut-Set Sums and Tree Processes
• Cutting Edges at Random in Large Recursive Trees
• Cutting resilient networks -- complete binary trees
• \(k\)-cut on paths and some trees
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent
• The cut-tree of large recursive trees

This page was built for publication: A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

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