[Zurück]


Beiträge in Tagungsbänden:

M. Drmota, M. Fuchs, H. Hwang, R. Neininger:
"External Profile of Symmetric Digital Search Trees";
in: "ANALCO17 Meeting on Analytic Algorithmics and Combinatorics", herausgegeben von: SIAM; SIAM - Society for Industrial and Applied Mathematics, 2017, ISBN: 978-1-61197-477-5, S. 124 - 130.



Kurzfassung englisch:
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.


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1137/1.9781611974775.12


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.