Skip Lists

Combinatorial problems of geometrically distributed random variables and applications in computer science.
H. Prodinger, editors: V. Strehl and R. Koenig,
Publications de l'IRMA (Strassbourg),
volume 30, pages 8795, 1993.

The path length of random skip lists.
P. Kirschenhofer and H. Prodinger,
Acta Informatica,
31:775792, 1994.

Analysis of an optimized search algorithm for skip lists.
P. Kirschenhofer, C. Martinez and H. Prodinger,
Theoretical Computer Science,
144:199200, 1995.

Combinatorics of geometrically distributed random variables: Lefttoright maxima.
H. Prodinger,
Discrete Mathematics,
page 253, 1996. presented at 5th FPSAC (Formal Power Series and Algebraic Combinatorics) Firenze.
(Back to the Homepage)