Home  Current  Past volumes  About  Login  Notify  Contact  Search  


References[1] David Aldous, Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228–266. MR1102319 [2] Søren Asmussen and Heinrich Hering, Branching Processes. Birkhäuser, Boston, MA, 1983. MR0701538 [3] K. B. Athreya, Preferential attachment random graphs with general weight function. Internet Math. 4 (2007), no. 4, 401–418. MR2522950 [4] Krishna B. Athreya, Arka P. Ghosh and Sunder Sethuraman, Growth of preferential attachment random graphs via continuoustime branching processes. Proc. Indian Acad. Sci. Math. Sci. 118 (2008), no. 3, 473–494. MR2450248 [5] Ricardo A. BaezaYates. Some average measures in mary search trees. Inform. Process. Lett. 25 (1987), no. 6, 375–381. MR0905782 [6] AlbertLászló Barabási and Réka Albert, Emergence of scaling in random networks. Science 286 (1999), no. 5439, 509–512. MR2091634 [7] Jürgen Bennies and Götz Kersting, A random walk approach to Galton–Watson trees. J. Theoret. Probab. 13 (2000), no. 3, 777–803. MR1785529 [8] François Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of increasing trees. CAAP’92 (Rennes, 1992), 24–48, Lecture Notes in Comput. Sci. 581, Springer, Berlin, 1992 MR1251994 [9] Jean Bertoin, Random Fragmentation and Coagulation Processes. Cambridge University Press, Cambridge, 2006. [10] Shankar Bhamidi, Universal techniques to analyze preferential attachment tree and networks: Global and local analysis. Preprint, 2007. http://www.unc.edu/~bhamidi/preferent.pdf [11] J. D. Biggins, The first and lastbirth problems for a multitype agedependent branching process. Advances in Appl. Probability 8 (1976), no. 3, 446–459. [12] J. D. Biggins, Chernoff’s theorem in the branching random walk. J. Appl. Probability 14 (1977), no. 3, 630–636. [13] J. D. Biggins, The growth and spread of the general branching random walk. Ann. Appl. Probab. 5 (1995), no. 4, 1008–1024. MR1384364 [14] J. D. Biggins, How fast does a general branching random walk spread? Classical and Modern Branching Processes (Minneapolis, MN, 1994), 19–39, Springer, New York, 1997. [15] J. D. Biggins and D. R. Grey, A note on the growth of random trees. Statist. Probab. Lett. 32 (1997), no. 4, 339–342. [16] Michael G. B. Blum and Olivier François, Minimal clade size and external branch length under the neutral coalescent. Adv. in Appl. Probab. 37 (2005), no. 3, 647–662. [17] Béla Bollobás, Oliver Riordan, Joel Spencer and Gábor Tusnády, The degree sequence of a scalefree random graph process. Random Structures Algorithms 18 (2001), no. 3, 279–290. [18] Miklós Bóna, kprotected vertices in binary search trees. Adv. in Appl. Math. 53 (2014), 1–11. [19] Miklós Bóna and Boris Pittel, On a random search tree: asymptotic enumeration of vertices by distance from leaves. Preprint, 2014. arXiv:1412.2796 [20] Nicolas Broutin and Luc Devroye, Large deviations for the weighted height of an extended class of trees. Algorithmica 46 (2006), nos 3–4, 271–297. [21] Nicolas Broutin, Luc Devroye and Erin McLeish, Weighted height of random trees. Acta Inform. 45 (2008), no. 4, 237–277. MR2403296 [22] Nicolas Broutin, Luc Devroye, Erin McLeish, and Mikael de la Salle, The height of increasing trees. Random Structures Algorithms 32 (2008), no. 4, 494–518. [23] Huilan Chang and Michael Fuchs, Limit theorems for patterns in phylogenetic trees. J. Math. Biol. 60 (2010), no. 4, 481–512. [24] Brigitte Chauvin and Michael Drmota, The random multisection problem, travelling waves and the distribution of the height of mary search trees. Algorithmica 46 (2006), nos 3–4, 299–327. [25] Birgitte Chauvin and Nicolas Pouyanne, mary search trees when m ≥ 27: a strong asymptotics for the space requirement. Random Structures Algorithms 24 (2004), 133–154. MR2035872 [26] HuaHuai Chern and HsienKuei Hwang, Phase changes in random mary search trees and generalized quicksort. Random Structures Algorithms 19 (2001), nos 3–4, 316–358. MR1871558 [27] HuaHuai Chern, HsienKuei Hwang and TsungHsi Tsai, An asymptotic theory for CauchyEuler differential equations with applications to the analysis of algorithms. J. Algorithms 44 (2002), no. 1, 177–225. [28] Maria Deijfen. Random networks with preferential growth and vertex death. J. Appl. Probab. 47 (2010), no. 4, 1150–1163. [29] Luc Devroye, A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 (1986), 489–498. [30] Luc Devroye, Branching processes in the analysis of the heights of trees. Acta Inform. 24 (1987), 277–298. MR0894557 [31] Luc Devroye, On the height of random mary search trees. Random Structures Algorithms 1 (1990), no. 2, 191–203. [32] Luc Devroye, Limit laws for local counters in random binary search trees. Random Structures Algorithms 2 (1991), no. 3, 303–315. [33] Luc Devroye, On the expected height of fringebalanced trees. Acta Inform. 30 (1993), 459–466. [34] Luc Devroye, Branching processes and their applications in the analysis of tree structures and tree algorithms. Probabilistic Methods for Algorithmic Discrete Mathematics, 249–314, eds. M. Habib, C. McDiarmid, J. Ramirez and B. Reed, Springer, Berlin, 1998. [35] Luc Devroye, Universal limit laws for depth in random trees. SIAM J. Comput. 28 (1998), 409–432. [36] Luc Devroye, Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput. 32 (2002/03), no. 1, 152–171. [37] Luc Devroye and Svante Janson, Protected nodes and fringe subtrees in some random trees. Electronic Communications Probability 19 (2014), no. 6, 1–10. [38] Luc Devroye, Colin McDiarmid and Bruce Reed, Giant components for two expanding graph processes. Mathematics and Computer Science, II (Versailles, 2002), 161–173, Birkhäuser, Basel, 2002. [39] R. A. Doney, A limit theorem for a class of supercritical branching processes. Journal of Applied Probability 9 (1972), no. 4, 707–724. [40] Michael Drmota, Random Trees. Springer, Vienna, 2009. [41] Michael Drmota, An analytic approach to the height of binary search trees II. J. ACM 50 (2003), no. 3, 333–374. MR2146358 [42] Michael Drmota, Michael Fuchs and YiWen Lee, Limit laws for the number of groups formed by social animals under the extra clustering model. (Extended abstract.) Proceedings, 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA’14 (Paris, 2014), 73–84, DMTCS Proceedings, 2014. [43] Michael Drmota, Bernhard Gittenberger, Alois Panholzer, Helmut Prodinger and Mark Daniel Ward, On the shape of the fringe of various types of random trees. Math. Methods Appl. Sci. 32 (2009), no. 10, 1207–1245. [44] Michael Drmota, Svante Janson and Ralph Neininger, A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 (2008), no. 1, 288–333. [45] Eric Durand, Michael G. B. Blum and Olivier François, Prediction of group patterns in social mammals based on a coalescent model. J. Theoret. Biol. 249 (2007), no. 2, 262–270. [46] Eric Durand and Olivier François, Probabilistic analysis of a genealogical model of animal group patterns. J. Math. Biol. 60 (2010), no. 3, 451–468. [47] William Feller, An Introduction to Probability Theory and Its Application, volume I, third edition, Wiley, New York, 1968. [48] James Allan Fill and Nevin Kapur, Transfer theorems and asymptotic distributional results for mary search trees. Random Structures Algorithms 26 (2005), no. 4, 359–391. [49] Philippe Flajolet, Xavier Gourdon and Conrado Martínez, Patterns in random binary search trees. Random Structures Algorithms 11 (1997), no. 3, 223–244. [50] Michael Fuchs, Subtree sizes in recursive trees and binary search trees: Berry–Esseen bounds and Poisson approximations. Combin. Probab. Comput. 17 (2008), no. 5, 661–680. [51] J. L. Gastwirth and P. K. Bhattacharya, Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Oper. Res. 32 (1984), no. 3, 527–536. [52] Carlo Friderico [Carl Friedrich] Gauss, Disquisitiones generales circa seriem infinitam 1 + x + xx + x^{3}+ etc., pars prior. Commentationes societatis regiae scientiarum Gottingensis recentiores II (1813). Reprinted in Werke, Vol. 3, 123–162, Göttingen, 1863. http://gdz.sub.unigoettingen.de/dms/load/toc/?PPN=PPN235999628 [53] Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. 2nd ed., AddisonWesley, Reading, MA, 1994. [54] Allan Gut, Probability: A Graduate Course, 2nd ed., Springer, New York, 2013. [55] Theodore E. Harris, The Theory of Branching Processes. SpringerVerlag, Berlin; PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. [56] Axel Heimbürger, Asymptotic distribution of twoprotected nodes in mary search trees. Master thesis, Stockholm University and KTH, 2014. divaportal.org/smash/get/diva2:748258/FULLTEXT01.pdf [57] Pascal Hennequin, Analyse en moyenne d’algorithmes, tri rapide et arbres de recherche. Ph.D. dissertation, École Polytechnique, Palaiseau, 1991. http://algo.inria.fr/AofA/Research/src/Hennequin.PhD.html [58] Remco van der Hofstad, Random Graphs and Complex Networks. Vol. I. Lecture notes. October 20, 2014 version. http://www.win.tue.nl/~rhofstad/NotesRGCN.html [59] Cecilia Holmgren and Svante Janson, Limit laws for functions of fringe trees for binary search trees and random recursive trees. Electron. J. Probab. 20 (2015), no. 4, 1–51. [60] Cecilia Holmgren and Svante Janson, Asymptotic distribution of twoprotected nodes in ternary search trees. Electron. J. Probab. 20 (2015), no. 9, 1–20. [61] Cecilia Holmgren and Svante Janson, Fringe trees, Crump–Mode–Jagers branching processes and mary search trees. arXiv:1601.03691 [62] Cecilia Holmgren, Svante Janson and Matas Šileikis, Multivariate normal limit laws for the numbers of fringe subtrees in mary search trees and preferential attachment trees. arXiv:1603.08125 [63] HsienKuei Hwang. Second phase changes in random mary search trees and generalized quicksort: convergence rates. Ann. Probab. 31 (2003), no. 2, 609–629. [64] Peter Jagers, Branching Processes with Biological Applications. John Wiley & Sons, London, 1975. [65] Peter Jagers and Olle Nerman, The growth and composition of branching populations. Adv. in Appl. Probab. 16 (1984), no. 2, 221–259. [66] Peter Jagers and Olle Nerman, The asymptotic composition of supercritical multitype branching populations. Séminaire de Probabilités, XXX, 40–54, Lecture Notes in Math. 1626, Springer, Berlin, 1996. [67] Svante Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110 (2004), 177–245. [68] Svante Janson, Asymptotic degree distribution in random recursive trees. Random Structures Algorithms 26 (2005), nos 1–2, 69–83. [69] Svante Janson, Simply generated trees, conditioned GaltonWatson trees, random allocations and condensation. Probability Surveys 9 (2012), 103–252. [70] Svante Janson, Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton–Watson trees. Random Structures Algorithms 48 (2016), no. 1, 57–101. [71] Svante Janson, Maximal clades in random binary search trees. Electron. J. Combin. 22 (2015), no. 1, Paper P1.31. [72] Svante Janson. Asymptotic normality in Crump–Mode–Jagers processes: the discrete time case. In preparation. [73] Svante Janson and Ralph Neininger, The size of random fragmentation trees. Probab. Theory Related Fields 142 (2008), nos 3–4, 399–442. [74] Norman L. Johnson, Adrienne W. Kemp, and Samuel Kotz, Univariate Discrete Distributions. 3rd ed., John Wiley & Sons, Hoboken, NJ, 2005. MR2163227 [75] Olav Kallenberg, Foundations of Modern Probability. 2nd ed., Springer, New York, 2002. [76] Ravi Kalpathy and Hosam Mahmoud, Degree profile of mary search trees: A vehicle for data structure compression. Probab. Engrg. Inform. Sci. 30 (2016), no. 1, 113–123. MR3436783 [77] J. F. C. Kingman, The first birth problem for an agedependent branching process. Ann. Probability 3 (1975), no. 5, 790–801. MR0400438 [78] Donald E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed., AddisonWesley, Reading, MA, 1998. MR3077154 [79] A. N. Kolmogoroff, Über das logarithmisch normale Verteilungsgesetz der Dimensionen der Teilchen bei Zerstückelung. C. R. (Doklady) Acad. Sci. URSS (N. S.) 31 (1941), 99–101. [80] P. L. Krapivsky and S. Redner, Organization of growing random networks. Phys. Rev. E 63 (2001), 066123. [81] P. L. Krapivsky, S. Redner, and F. Leyvraz, Connectivity of Growing Random Networks. Phys. Rev. Lett. 85 (2000), 4629–4632. [82] Markus Kuba and Alois Panholzer, Isolating a leaf in rooted trees via random cuttings. Ann. Comb. 12 (2008), no. 1, 81–99. [83] William Lew and Hosam M. Mahmoud, The joint distribution of elastic buckets in multiway search trees. SIAM J. Comput. 23 (1994), no. 5, 1050–1074. [84] Jiang Lu and Qilin Feng, Strong consistency of the number of vertices of given degrees in nonuniform random recursive trees. Yokohama Math. J. 45 (1998), no. 1, 61–69. [85] Hosam M. Mahmoud, Evolution of Random Search Trees. John Wiley & Sons, New York, 1992. [86] Hosam M. Mahmoud, A strong law for the height of random binary pyramids. Ann. Appl. Probab. 4 (1994), no. 3, 923–932. [87] Hosam M. Mahmoud and Boris Pittel, Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10 (1989), no. 1, 52–75. [88] Hosam M. Mahmoud and R. T. Smythe, Asymptotic joint normality of outdegrees of nodes in random recursive trees. Random Structures Algorithms 3 (1992), no. 3, 255–266. [89] Hosam M. Mahmoud, R. T. Smythe and Jerzy Szymański, On the structure of random planeoriented recursive trees and their branches. Random Structures Algorithms 4 (1993), no. 2, 151–176. [90] Hosam M. Mahmoud and Mark Daniel Ward, Asymptotic distribution of twoprotected nodes in random binary search trees. Appl. Math. Lett. 25 (2012), no. 12, 2218–2222. [91] Hosam M. Mahmoud and Mark D. Ward, Asymptotic properties of protected nodes in random recursive trees. J. Appl. Probab. 52 (2015), no. 1, 290–297. [92] T. F. Móri, On random trees. Studia Sci. Math. Hungar. 39 (2002), nos 1–2, 143–155. [93] Richard Muntz and Robert Uzgalis, Dynamic storage allocation for binary search trees in a twolevel memory. Proceedings of the Princeton Conference on Information Sciences and Systems 4 (1971), 345–349. [94] Olle Nerman, On the convergence of supercritical general (CMJ) branching processes. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 3, 365–395. [95] Olle Nerman and Peter Jagers, The stable double infinite pedigree process of supercritical branching populations. Z. Wahrsch. Verw. Gebiete 65 (1984), no. 3, 445–460. [96] Jacques Neveu, Arbres et processus de Galton–Watson. Ann. Inst. H. Poincaré Probab. Statist. 22, no. 2 (1986), 199–207. [97] NIST Handbook of Mathematical Functions. Edited by Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert and Charles W. Clark. Cambridge Univ. Press, 2010. Also available as NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/ [98] Roberto Oliveira and Joel Spencer, Connectivity transitions in networks with superlinear preferential attachment. Internet Math. 2 (2005), no. 2, 121–163. [99] Anthony G. Pakes, Limit laws for UGROW random graphs. Statist. Probab. Lett. 83 (2013), no. 12, 2607–2614. MR3118202 [100] Alois Panholzer and Helmut Prodinger, Level of nodes in increasing trees revisited. Random Structures Algorithms 31 (2007), no. 2, 203–226. [101] Boris Pittel, On growing random binary trees. J. Math. Anal. Appl. 103 (1984), no. 2, 461–480. [102] Boris Pittel, Note on the heights of random recursive trees and random mary search trees, Random Structures Algorithms 5 (1994), 337–347. [103] Bruce Reed, The height of a random binary search tree. J. ACM 50 (2003), no. 3, 306–332. [104] Anna Rudas and Bálint Tóth, Random tree growth with branching processes – a survey. Handbook of LargeScale Random Networks, 171–202, Bolyai Soc. Math. Stud. 18, Springer, Berlin, 2009. [105] Anna Rudas, Bálint Tóth and Benedek Valkó, Random trees and general branching processes. Random Structures Algorithms 31 (2007), no. 2, 186–202. MR2343718 [106] Herbert A. Simon, On a class of skew distribution functions. Biometrika 42 (1955), 425–440. [107] Jerzy Szymański, On a nonuniform random recursive tree. Annals of Discrete Math. 33 (1987), 297–306. [108] G. Udny Yule, A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F.R.S. Philos. Trans. Roy. Soc. B 213 (1925), 21–87. 

Home  Current  Past volumes  About  Login  Notify  Contact  Search Probability Surveys. ISSN: 15495787 