A probabilistic analysis of some tree algorithms

DOI10.1214/105051605000000494zbMath1110.68174arXivmath/0412188OpenAlexW2077904203MaRDI QIDQ2496496

Hanène Mohamed, Philippe Robert

Publication date: 10 July 2006

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

data structuresrenewal theoremtriessplitting algorithmsdivide and conquer algorithmsasymptotic oscillating behaviorunusual laws of large numbers

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Stochastic network models in operations research (90B15) Markov renewal processes, semi-Markov processes (60K15) Data structures (68P05) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20)

Related Items (6)

Central limit theorems for additive functionals and fringe trees in tries ⋮ The total path length of split trees ⋮ Dynamic tree algorithms ⋮ Analysis of Steiner subtrees of random trees for traceroute algorithms ⋮ Renewal theory in the analysis of tries and strings ⋮ On the Asymptotic Distribution of Nucleation Times of Polymerization Processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Asymptotical growth of a class of random trees
• Sur certaines martingales de Benoit Mandelbrot
• Moments, continuity, and multifractal analysis of Mandelbrot martingales
• Inequalities for the overshoot
• Analysis of an asymmetric leader election algorithm
• On generalized multiplicative cascades
• On the moments of a distribution defined by the Gaussian polynomials.
• Universal asymptotics for random tries and PATRICIA trees
• Dynamical sources in information theory: A general analysis of trie structures
• Exchangeable and partially exchangeable random partitions
• Random Recursive Constructions: Asymptotic Geometric and Topological Properties
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• Tree algorithms for packet broadcast channels
• Analysis of a stack algorithm for random multiple-access communication
• Born again group testing: Multiaccess communications
• Universal Limit Laws for Depths in Random Trees
• A general decomposition theory for random cascades
• Information theory and communication networks: an unconsummated union
• New results on the size of tries
• Limit laws for the height in PATRICIA tries
• On the asymptotic behavior of some algorithms
• On Excess Over the Boundary
• Random fractal strings: Their zeta functions, complex dimensions and spectral asymptotics
• Probability
• Homogeneous fragmentation processes

This page was built for publication: A probabilistic analysis of some tree algorithms