Projects per year
Abstract
In this paper, we introduce a model of depth-weighted random recursive trees, created by recursively joining a new leaf to an existing vertex v. In this model, the probability of choosing v depends on its depth in the tree. In particular, we assume that there is a function f such that if k has depth k then its probability of being chosen is proportional to f(k). We consider the expected value of the diameter of this model as determined by f, and for various increasing f we find expectations that range from polylogarithmic to linear.
Original language | English |
---|---|
Pages (from-to) | 851-866 |
Number of pages | 16 |
Journal | Random Structures and Algorithms |
Volume | 56 |
Issue number | 3 |
DOIs | |
Publication status | Published - May 2020 |
Keywords
- height
- random recursive trees
- random trees
Projects
- 1 Finished
-
Advances in the analysis of random structures and their applications: relationships among models
Wormald, N. (Primary Chief Investigator (PCI))
Australian Research Council (ARC)
1/08/12 → 31/12/17
Project: Research