A probabilistic analysis of some tree algorithms

DOI10.1214/105051605000000494zbMath1110.68174arXivmath/0412188MaRDI 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 structures; renewal theorem; tries; splitting algorithms; divide and conquer algorithms; asymptotic oscillating behavior; unusual laws of large numbers

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B15: Stochastic network models in operations research

60K15: Markov renewal processes, semi-Markov processes

68P05: Data structures

60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)

Related Items

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

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