Oberwolfach Reports


Full-Text PDF (444 KB) | Introduction as PDF | Metadata | Table of Contents | OWR summary
Volume 8, Issue 2, 2011, pp. 1241–1286
DOI: 10.4171/OWR/2011/23

Published online: 2011-12-07

Mini-Workshop: Random Trees, Information and Algorithms

Ralph Neininger and Wojciech Szpanowski[1]

(1) Purdue University, West Lafayette, USA

The subject of this Mini-Workshop is the probabilistic analysis of random tree models that originate from applications in Computer Science. Emphasis is put on their connections to algorithms and information theory. Trees with a stochastic growth dynamic appear in Computer Science as data structures, in the context of coding schemes as well as connected to fundamental algorithms such as sorting, searching and selecting. The focus of this Mini-Workshop is on probabilistic and analytic techniques that have been developed recently in the asymptotic analysis of random trees such as martingale methods, connections to branching random walks, the contraction method, the method of moments as well as various techniques based on generating functions.

No keywords available for this article.

Neininger Ralph, Szpanowski Wojciech: Mini-Workshop: Random Trees, Information and Algorithms. Oberwolfach Rep. 8 (2011), 1241-1286. doi: 10.4171/OWR/2011/23