A probabilistic analysis of some tree algorithms
From MaRDI portal
Publication:2496496
DOI10.1214/105051605000000494zbMath1110.68174arXivmath/0412188MaRDI QIDQ2496496
Philippe Robert, Hanène Mohamed
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
data structures; renewal theorem; tries; splitting algorithms; divide and conquer algorithms; asymptotic oscillating behavior; unusual laws of large numbers
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
The total path length of split trees, Renewal theory in the analysis of tries and strings, 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
