Dynamic tree algorithms

DOI10.1214/09-AAP617zbMath1183.68764arXiv0809.3577MaRDI QIDQ2268721

Hanène Mohamed, Philippe Robert

Publication date: 8 March 2010

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

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

zbMATH Keywords

renewal theorems; tree structures; random access networks; auto-regressive processes; Capetanakis-Tsybakov-Mikhailov algorithm

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B15: Stochastic network models in operations research

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

Cites Work

• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Random multiple-access stack algorithm
• On the probability of abandonment in queues with limited sojourn and waiting times
• A probabilistic analysis of some tree algorithms
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels
• Tree algorithms for packet broadcast channels
• Analysis of a stack algorithm for random multiple-access communication
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Analysis of contention tree algorithms
• Information theory and communication networks: an unconsummated union
• Homogeneous fragmentation processes