Contributions to Proceedings:
M. Drmota, M. Fuchs, H. Hwang, R. Neininger:
"External Profile of Symmetric Digital Search Trees";
in: "ANALCO17 Meeting on Analytic Algorithmics and Combinatorics",
issued by: SIAM;
SIAM - Society for Industrial and Applied Mathematics,
2017,
ISBN: 978-1-61197-477-5,
124
- 130.
English abstract:
The external profile is among the first examined shape parameters of symmetric digital search trees in connection with the performance of unsuccessful search of a random query in the early 1970s. However, finer and important properties beyond the mean such as the variance and the limit law have remained unknown. In this extended abstract, we describe the first results for the asymptotic variance and the limit law of the external profile. In particular, the analysis of the variance turns out to be highly demanding and nontrivial, and we need diverse techniques from analytic combinatorics to unveil its asymptotic behaviors.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1137/1.9781611974775.12
Created from the Publication Database of the Vienna University of Technology.