41 citations · 108 across the 7 of their papers we have counts for
6 papers · 1 filter
A repertoire for additive functionals of uniformly distributed m-ary search trees
James Allen Fill, Nevin Kapur
Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on -ary search trees on…
Destruction of very simple trees
James Allen Fill, Nevin Kapur, Alois Panholzer
We consider the total cost of cutting down a random rooted tree chosen from a family of so-called very simple trees (which include ordered trees, -ary trees, and Cayley trees);…
The space requirement of m-ary search trees: distributional asymptotics for m >= 27
James Allen Fill, Nevin Kapur
We study the space requirement of -ary search trees under the random permutation model when is fixed. Chauvin and Pouyanne have shown recently that , the space…
Limiting distributions for additive functionals on Catalan trees
James Allen Fill, Nevin Kapur
Additive tree functionals represent the cost of many divide-and-conquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the…
Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees
James Allen Fill, Nevin Kapur
We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of…
Additive functionals on random search trees
Nevin Kapur
Search trees are fundamental data structures in computer science. We study functionals on random search trees that satisfy recurrence relations of a simple additive form. Many impo…