The height of depth‐weighted random recursive trees. Issue 3 (12th January 2020)

• Record Type: Journal Article
• Authors: Leckey, Kevin; Mitsche, Dieter; Wormald, Nick
• Is Part Of: Random structures & algorithms. Volume 56:Issue 3(2020)
• Page Start: 851
• Page End: 866
• Publication Date: 2020-01-12
• Subjects: random trees -- random recursive trees -- height; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20901
• Languages: English
• ISSNs: 1042-9832

Abstract

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 v 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.