×

zbMATH — the first resource for mathematics

Profiles of random trees: plane-oriented recursive trees. (English) Zbl 1115.05083
Summary: 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).

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albert, Rev Mod Phys 74 pp 47– (2002)
[2] Barabási, Science 286 pp 509– (1999)
[3] , , Varieties of increasing trees, In CAAP’92 (Rennes, 1992), Lecture Notes in Computer Science, 581, Springer, Berlin, 1992, pp. 24–48.
[4] Biggins, Stat Probab Lett 32 pp 339– (1997)
[5] , ” Mathematical results on scale-free random graphs,” Handbook of Graphs And Networks, Wiley-VCH, Weinheim, 2003, pp. 1–34.
[6] Bollobás, Phys Rev E 69 (2004)
[7] Bollobás, Random Struct Algor 18 pp 279– (2001)
[8] Chen, Eur J Combinator 15 pp 513– (1994)
[9] Chen, Inform Process Lett 51 pp 129– (1994)
[10] Chen, Int J Found Comp Sci 5 pp 99– (1994)
[11] Chern, Random Struct Algor 19 pp 316– (2001)
[12] Chern, J Algor 44 pp 177– (2002)
[13] da Fonseca, Inform Process Lett 85 pp 165– (2003)
[14] Devroye, Ann Appl Probab 16 pp 886– (2005)
[15] Dorogovtsev, Adv Phys 51 pp 1079– (2002)
[16] Drmota, Random Struct Algor 10 pp 421– (1997)
[17] Drmota, SIAM J Discrete Math 19 pp 19– (2005)
[18] Drmota, Adv Appl Probab 37 pp 321– (2005)
[19] Fill, Theor Comp Sci 326 pp 69– (2004)
[20] Flajolet, Algorithmica 31 pp 361– (2001)
[21] Flajolet, SIAM J Discrete Math 3 pp 216– (1990)
[22] Fredman, Algorithmica 1 pp 111– (1986)
[23] Fuchs, Algorithmica (2005)
[24] ” The number of descendants in simply generated random trees,” Mathematics and Computer Science, (Versailles, 2000), Birkhäuser, Basel, pp. 65–73. · Zbl 0965.68070
[25] Grossman, J Alg 126 pp 184– (1989)
[26] Hwang, J Combinator Theor A 71 pp 343– (1995)
[27] Janson, Random Struct Algor 26 pp 69– (2005)
[28] Jeong, Europhys Lett 61 pp 567– (2003)
[29] The Art of Computer Programming, Volume 1, Fundamental Algorithms, Second ed., Addison-Wesley, Reading, MA, 1997.
[30] Lu, Yokohama Math J 45 pp 61– (1998)
[31] Mahmoud, J Comput Appl Math 41 pp 237– (1992)
[32] Mahmoud, Random Struct Algor 4 pp 151– (1993)
[33] Móri, Stud Sci Math Hung 39 pp 143– (2002)
[34] Móri, Combinator Probab Comput 14 pp 339– (2005)
[35] Morris, Combinator Probab Comp 13 pp 677– (2004)
[36] Newman, SIAM Rev 45 pp 167– (2003)
[37] Panholzer, Random Struct Algor 26 pp 84– (2005)
[38] Panholzer, Discrete Math Theoret Comp Sci 6 pp 437– (2004)
[39] Pittel, Random Struct Algor 5 pp 337– (1994)
[40] Prodinger, Int J Found Comp Sci 7 pp 293– (1996)
[41] Prodinger, Electron J Combinator 3 (1996)
[42] Prodinger, Discrete Appl Math 5 pp 223– (1983)
[43] Smythe, Theor Probab Math Statist 51 pp 1– (1995)
[44] Stepanov, Theor Probab Appl 14 pp 65– (1969)
[45] Szabó, Phys Rev E 66 (2002)
[46] ” On a nonuniform random recursive tree,” In Random Graphs ’85 (Poznań, 1985), North-Holland Mathematics Studies, 144, Amsterdam, North-Holland, pp. 297–306.
[47] Szymański, Random Struct Algor 26 pp 224– (2005)
[48] Takács, J Appl Math Stoch Anal 4 pp 175– (1991)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.