The height of depth-weighted random recursive trees

Kevin Leckey, Dieter Mitsche, Nick Wormald

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)851-866
Number of pages16
JournalRandom Structures & Algorithms
Volume56
Issue number3
DOIs
Publication statusPublished - May 2020

Keywords

  • height
  • random recursive trees
  • random trees

Cite this