The height of depth-weighted random recursive trees

被引:2
作者
Leckey, Kevin [1 ]
Mitsche, Dieter [2 ,3 ,4 ]
Wormald, Nick [5 ]
机构
[1] Tech Univ Dortmund, Fac Stat, Dortmund, Germany
[2] Inst Camille Jordan, Villeurbanne, France
[3] Univ Lyon, Lyon, France
[4] Univ Jean Monnet, St Etienne, France
[5] Monash Univ, Sch Math, Melbourne, Vic, Australia
基金
澳大利亚研究理事会;
关键词
random trees; random recursive trees; height;
D O I
10.1002/rsa.20901
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:851 / 866
页数:16
相关论文
共 12 条