Open Access

Limit laws for two distance-based indices in random recursive tree models


Cite

[1] R. Dobrow, J. A. Fill, Total path length for random recursive trees. Random graphs and combinatorial structures (Oberwolfach, 1997). Combin. Probab. Comput. 8, 4 (1999) 317–333. ⇒4610.1017/S0963548399003855 Search in Google Scholar

[2] M. Drmota, Random Trees, An Interplay Between Combinatorics and Probability, Springer, Wien-New York, 2009. ⇒3610.1007/978-3-211-75357-6 Search in Google Scholar

[3] W.-C. Chen, W.-C. Ni, On the average altitude of heap-ordered trees, Int. J. Found. Comput. Sci. 5, 1 (1994) 99–109. ⇒4010.1142/S0129054194000062 Search in Google Scholar

[4] B. Gittenberger, The number of descendants in simply generated random trees. In:Gardy, D., Mokkadem, A.(eds) Mathematics and Computer Science. Trends in Mathematics. Birkhäuser, Basel. pp. 65–73. https://doi.org/10.1007/978-3-0348-8405-1_6 ⇒3910.1007/978-3-0348-8405-1_6 Search in Google Scholar

[5] P. Hall, C. C. Heyde, Martingale Limit Theory and its Application,Academic Press, New York, 1980. ⇒47 Search in Google Scholar

[6] H.-K. Hwang, Profiles of random trees: plane-oriented recursive trees. Random Structures Algorithms. 30, 3 (2007) 380–413. ⇒37, 4310.1002/rsa.20139 Search in Google Scholar

[7] H.-K. Hwang, R. Neininger, Phase change of limit laws in the quicksort recurrence under varying toll functions. SIAM J. Comput. 31 (2002) 1687–1722. ⇒ 4110.1137/S009753970138390X Search in Google Scholar

[8] H. M. Mahmoud, Distances in random plane-oriented recursive trees, J. Comput. Appl. Math. 41 (1992) 237–245. ⇒37, 4610.1016/0377-0427(92)90252-S Search in Google Scholar

[9] H. M. Mahmoud, Limiting distributions for path lengths in recursive trees. Probab. Eng. Inform. Sci. 5 (1991) 53–59. ⇒3610.1017/S0269964800001881 Search in Google Scholar

[10] H. Mahmoud, R.T. Smythe, J. Szymański, On the structure of random plane-oriented recursive trees and their branches. Random Structures Algorithms. 4, 2 (1993) 151–176. ⇒3710.1002/rsa.3240040204 Search in Google Scholar

[11] D. Najock, C.C. Heyde, On the number of terminal vertices in certain random trees with an application to stemma construction in philology. J. Appl. Probab. 19, 3 (1982) 675–680. ⇒3610.2307/3213526 Search in Google Scholar

[12] A. Panholzer, H. Prodinger, Level of nodes in increasing trees revisited, Random Structures Algorithms. 31, 2 (2007) 203–226. ⇒36, 3710.1002/rsa.20161 Search in Google Scholar

[13] S. Rachev, L. Rüschendorf, Probability metrics and recursive algorithms, Adv. Appl. Probab. 27 (1995) 770–799. ⇒4110.2307/1428133 Search in Google Scholar

[14] U. Rösler, A limit theorem for “quicksort”, RAIRO-Inform. Theor. Appl. 25 (1991) 85–100. ⇒4110.1051/ita/1991250100851 Search in Google Scholar

[15] U. Rösler, The analysis of stochastic divide and conquer algorithms, Algorith-mica. 29 (2001) 238–261. ⇒41, 4410.1007/BF02679621 Search in Google Scholar

[16] U. Rösler, L. Rüschendorf, The contraction method for recursive algorithms, Algorithmica. 29 (2001) 3–33. ⇒4110.1007/BF02679611 Search in Google Scholar

[17] M. J. Sackin, “Good” and “bad” phenograms, Systematic Zoology. 21 (1972) 225–226. https://doi.org/10.1093/sysbio/21.2.225 ⇒3610.1093/sysbio/21.2.225 Search in Google Scholar

[18] J. Szymański, On the complexity of algorithms on recursive trees. Theoret. Comput. Sci. 74, 3 (1990) 355–361. ⇒3810.1016/0304-3975(90)90084-U Search in Google Scholar

eISSN:
2066-7760
Language:
English
Publication timeframe:
2 times per year
Journal Subjects:
Computer Sciences, other