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 87-95, 1993.
The path length of random skip lists. P. Kirschenhofer and H. Prodinger, Acta Informatica, 31:775-792, 1994.
Analysis of an optimized search algorithm for skip lists. P. Kirschenhofer, C. Martinez and H. Prodinger, Theoretical Computer Science, 144:199-200, 1995.
Combinatorics of geometrically distributed random variables: Left-to-right maxima. H. Prodinger, Discrete Mathematics, page 253, 1996. presented at 5th FPSAC (Formal Power Series and Algebraic Combinatorics) Firenze.

(Back to the Homepage)