Name
Abstract | ||
|---|---|---|
We study the average size of the minimal directed acyclic graph (DAG) with respect to so-called leaf-centric binary tree sources as studied by Zhang, Yang, and Kieffer. A leaf-centric binary tree source induces for every $n geq 2$ a probability distribution on all binary trees with $n$ leaves. We generalize a result shown by Flajolet, Gourdon, Martinez and Devroye according to which the average size of the minimal DAG of a binary tree that is produced by the binary search tree model is $Theta(n / log n)$. |
Year | Venue | DocType |
|---|---|---|
2018 | MFCS | Conference |
Volume | Citations | PageRank |
abs/1804.10396 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Louisa Seelbach Benkner | 1 | 0 | 1.69 |
| Markus Lohrey | 2 | 903 | 75.40 |