Paper Info
Title
Profiles of random trees: Plane-oriented recursive trees
Abstract
We derive several limit results for the profile of random plane-oriented recursive trees. These include the limit distribution of the normalized profile, asymptotic bimodality of the variance, asymptotic approximation to the expected width, and the correlation coefficients of two level sizes. Most of our proofs are based on a method of moments. We also discover an unexpected connection between the profile of plane-oriented recursive trees (with logarithmic height) and that of random binary trees (with height proportional to the square root of tree size). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 An extended abstract of this paper appears in a special issue (DMTCS Proceedings Volume AD, 2005, pp. 193–200) of Discrete Mathematics and Theoretical Computer Science for the 2005 International Conference on the Analysis of Algorithms, Barcelona, June 6–10, 2005.
Year
DOI
Venue
2007
10.1002/rsa.v30:3
Random Structures and Algorithms
Keywords
DocType
Volume
logarithmic height,limit result,limit distribution,plane-oriented recursive tree,asymptotic approximation,normalized profile,random binary tree,asymptotic bimodality,random plane-oriented recursive tree,random tree,dmtcs proceedings volume
Journal
30
Issue
ISSN
Citations 
3
1042-9832
11
PageRank 
References 
Authors
0.73
29
1
Name
Order
Citations
PageRank
Hsien-Kuei Hwang136538.02