4 citations · 5 across the 5 of their papers we have counts for
7 papers
A limit theorem for the six-length of random functional graphs with a fixed degree sequence
Kevin Leckey, Nicholas Wormald
We obtain results on the limiting distribution of the six-length of a random functional graph, also called a functional digraph or random mapping, with given in-degree sequence. Th…
Process convergence for the complexity of Radix Selection on Markov sources
Kevin Leckey, Ralph Neininger, Henning Sulzbach
A fundamental algorithm for selecting ranks from a finite subset of an ordered set is Radix Selection. This algorithm requires the data to be given as strings of symbols over an or…
On Densities for Solutions to Stochastic Fixed Point Equations
Kevin Leckey
We consider systems of stochastic fixed-point equations that arise in the asymptotic analysis of random recursive structures and algorithms such as Quicksort, generalized Pólya urn…
A Limit Theorem for Radix Sort and Tries with Markovian Input
Kevin Leckey, Ralph Neininger, Wojciech Szpankowski
Tries are among the most versatile and widely used data structures on words. In particular, they are used in fundamental sorting algorithms such as radix sort which we study in thi…
Analysis of radix selection on Markov sources
Kevin Leckey, Ralph Neininger, Henning Sulzbach
The complexity of the algorithm Radix Selection is considered for independent data generated from a Markov source. The complexity is measured by the number of bucket operations req…
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model
Kevin Leckey, Ralph Neininger, Wojciech Szpankowski
Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used…
Asymptotic analysis of Hoppe trees
Kevin Leckey, Ralph Neininger
We introduce and analyze a random tree model associated to Hoppe's urn. The tree is built successively by adding nodes to the existing tree when starting with the single root node.…