A probabilistic analysis of some tree algorithms
From MaRDI portal
Abstract: In this paper a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to the usual complex analysis techniques. This approach gives a unified probabilistic treatment of these questions. It simplifies and extends some of the results known in this domain.
Recommendations
Cites work
- scientific article; zbMATH DE number 987641 (Why is no real title available?)
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3978406 (Why is no real title available?)
- scientific article; zbMATH DE number 3659453 (Why is no real title available?)
- scientific article; zbMATH DE number 53571 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 3434889 (Why is no real title available?)
- scientific article; zbMATH DE number 815575 (Why is no real title available?)
- scientific article; zbMATH DE number 873409 (Why is no real title available?)
- scientific article; zbMATH DE number 1399886 (Why is no real title available?)
- scientific article; zbMATH DE number 227027 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- A general decomposition theory for random cascades
- Analysis of a stack algorithm for random multiple-access communication
- Analysis of an asymmetric leader election algorithm
- Asymptotical growth of a class of random trees
- Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
- Born again group testing: Multiaccess communications
- Dynamical sources in information theory: A general analysis of trie structures
- Exchangeable and partially exchangeable random partitions
- Homogeneous fragmentation processes
- Inequalities for the overshoot
- Information theory and communication networks: an unconsummated union
- Limit laws for the height in PATRICIA tries
- Mellin transforms and asymptotics: Harmonic sums
- Moments, continuity, and multifractal analysis of Mandelbrot martingales
- New results on the size of tries
- On Excess Over the Boundary
- On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
- On generalized multiplicative cascades
- On the asymptotic behavior of some algorithms
- On the moments of a distribution defined by the Gaussian polynomials.
- Probability. Theory and examples.
- Random Recursive Constructions: Asymptotic Geometric and Topological Properties
- Random fractal strings: Their zeta functions, complex dimensions and spectral asymptotics
- Sur certaines martingales de Benoit Mandelbrot
- Techniques in fractal geometry
- Tree algorithms for packet broadcast channels
- Universal Limit Laws for Depths in Random Trees
- Universal asymptotics for random tries and PATRICIA trees
Cited in
(23)- Probabilistic analysis of algorithms for the Dutch national flag problem
- The total path length of split trees
- Analysis of Steiner subtrees of random trees for traceroute algorithms
- Algorithms, random tree models and combinatorial objects
- An algorithm for the Lorenz measure in locational decisions on trees
- Mini-workshop: Random trees, information and algorithms. Abstracts from the mini-workshop held April 24--30, 2011
- A survey on performance analysis of warehouse carousel systems
- scientific article; zbMATH DE number 1456964 (Why is no real title available?)
- scientific article; zbMATH DE number 3954271 (Why is no real title available?)
- On the asymptotic behavior of some algorithms
- On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search
- Dynamic tree algorithms
- scientific article; zbMATH DE number 1444332 (Why is no real title available?)
- Central limit theorems for additive functionals and fringe trees in tries
- scientific article; zbMATH DE number 6605055 (Why is no real title available?)
- Renewal theory in the analysis of tries and strings
- On the asymptotic distribution of nucleation times of polymerization processes
- Probability, trees and algorithms. Abstracts from the workshop held November 2--8, 2014.
- Analysis of the space of search trees under the random insertion algorithm
- Probabilistic analysis of vantage point trees
- On a tail bound for analyzing random trees
- scientific article; zbMATH DE number 15993 (Why is no real title available?)
- Analytical estimates and proof of the scale-free character of efficiency and improvement in Barabási-Albert trees
This page was built for publication: A probabilistic analysis of some tree algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496496)
