A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
From MaRDI portal
Publication:405180
zbMath1300.68021MaRDI QIDQ405180
Publication date: 4 September 2014
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p69
moments; Wiener index; digital trees; multivariate limit laws; nodes of fixed out-degree; total path length
68W40: Analysis of algorithms
60F05: Central limit and other weak theorems
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
68P05: Data structures
Related Items
Dependence between path-length and size in random digital trees, The Wiener Index of Random Digital Trees, On 2-protected nodes in random digital trees, Asymptotic normality for the size of graph tries built from M-ary tree labelings, On the variety of shapes in digital trees
Uses Software
Cites Work
- Mellin transforms and asymptotics: Harmonic sums
- Mellin transforms and asymptotics: Finite differences and Rice's integrals
- On the variance of a class of inductive valuations of data structures for digital search
- Analytical depoissonization and its applications
- A general limit theorem for recursive algorithms and combinatorial structures
- Dynamical sources in information theory: Fundamental intervals and word prefixes
- Dynamical sources in information theory: A general analysis of trie structures
- An analytic approach to the asymptotic variance of trie statistics and related structures
- Size and path length of Patricia tries: Dynamical sources context
- A Generalisation of Stirling's Formula.
- Asymptotic variance of random symmetric digital search trees
- Profiles of Tries
- A multivariate view of random bucket digital search trees
- The Variance of the Number of 2-Protected Nodes in a Trie
- The Wiener Index of Random Digital Trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
