×

zbMATH — the first resource for mathematics

The height of increasing trees. (English) Zbl 1148.05024
Summary: We extend results about heights of random trees [L. Devroye, J. Assoc. Comput. Mach. 33, No. 3, 489–498 (1986; Zbl 0741.05062), SIAM J. Comp. 28, No. 2, 409–432 (1998; Zbl 0915.68089)]. In this paper, a general split tree model is considered in which the normalized subtree sizes of nodes converge in distribution. The height of these trees is shown to be in probability asymptotic to \(c \log n\) for some constant \(c\). We apply our results to obtain a law of large numbers for the height of all polynomial varieties of increasing trees [F. Bergeron, P. Flajolet and B. Salvy, Lect. Not. Comp. Sci. 581, 24–48 (1992)].

MSC:
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] and , Branching processes, Springer, Berlin, 1972. · Zbl 0259.60002 · doi:10.1007/978-3-642-65371-1
[2] Barabási, Science 286 pp 509– (1999)
[3] Bergeron, CAAP Lect Notes Comput Sci 581 pp 24– (1992) · doi:10.1007/3-540-55251-0_2
[4] Biggins, Adv Appl Probab 8 pp 446– (1976)
[5] Biggins, J Appl Probab 14 pp 630– (1977)
[6] Biggins, Stat Probab Lett 32 pp 339– (1997)
[7] Probability and Measure, 3rd edition, Wiley, New York, 1995.
[8] Broutin, Algorithmica 46 pp 271– (2006)
[9] Chernoff, Ann Math Stat 23 pp 493– (1952)
[10] Coffman, Commun ACM 13 pp 427– (1970)
[11] Sur un nouveau théorème-limite de la théorie des probabilités. In, Colloque Consacré à la Théorie des Probabilités, volume 736, Hermann, Paris, 1938, pp. 5–23.
[12] and , Large Deviation Techniques and Applications, 2nd edition, Springer Verlag, 1998. · doi:10.1007/978-1-4612-5320-4
[13] and , Large Deviations, American Mathematical Society, Providence, RI, 1989.
[14] Devroye, J ACM 33 pp 489– (1986)
[15] Devroye, Acta Inform 24 pp 277– (1987)
[16] Branching processes and their application in the analysis of tree structures and tree algorithms, In, , , and , editors, Probabilistic methods for algorithmic discrete mathematics, volume 16 of Springer series on algorithms and combinatorics, Springer, Berlin, 1998, pp. 249–314. · Zbl 0924.60077
[17] Devroye, SIAM J Comp 28 pp 409– (1998)
[18] Drmota, J ACM 50 pp 333– (2003)
[19] The height of increasing trees, 2006. Annals of Combinatorics, to appear.
[20] , and , Statistical Distributions, 3rd edition, Wiley, New York, NY, 2000.
[21] Fredkin, Commun ACM 3 pp 490– (1960)
[22] and , Probability of Random Processes, 2nd edition, Oxford University Press, Oxford, 2001.
[23] The Theory of Branching Processes, Springer, Berlin, 1963. · doi:10.1007/978-3-642-51866-9
[24] Janson, Fourth Colloquium Math Comput Sci Algorithms, Trees Combin Probab pp 331– (2006)
[25] Kennedy, J Appl Probab 12 pp 800– (1975)
[26] The Art of Computer Programming: Sorting and Searching, volume 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[27] Branching processes and random trees. In, Problems in Cybernetics, Combinatorial Analysis and Graph Theory (in Russian), Moscow, Nauka, 1980, pp. 85–97. · Zbl 0502.60012
[28] Random Mappings, Optimization Software, New York, 1986.
[29] Konheim, Discrete Math 4 pp 57– (1973)
[30] Łuczak, Random Struct Algorithms 24 pp 420– (2004)
[31] Mahmoud, J Computat Appl Math 41 pp 237– (1992)
[32] Mahmoud, Random Struct Algorithms 4 pp 151– (1993)
[33] Martínez, SIAM J Comput 31 pp 683– (2001)
[34] Meir, Can J Math 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[35] Counting Labelled Trees, Number 1 in Canadian Mathematical Monographs. Canadian Mathematical Congress, Montreal, 1970.
[36] Morrison, J ACM 15 pp 514– (1968)
[37] Panholzer, Discrete Math Theor Comput Sci 6 pp 437– (2004)
[38] Panholzer, Random Struct Algorithms 31 pp 203– (2007)
[39] Pittel, J Math Anal Appl 103 pp 461– (1984)
[40] Pittel, Ann Probab 13 pp 414– (1985)
[41] Pittel, Random Struct Algorithms 5 pp 337– (1994)
[42] Prodinger, Discrete Appl Math 5 pp 222– (1983)
[43] How tall is a tree? In, STOC ’00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM Press, 2000, New York, NY, pp. 479–483.
[44] Reed, J ACM 50 pp 306– (2003)
[45] Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0932.90001 · doi:10.1515/9781400873173
[46] Smythe, Theor Probab Math Stat 51 pp 1– (1995)
[47] Average Case Analysis of Algorithms on Sequences, Wiley, New York, 2001. · doi:10.1002/9781118032770
[48] On a non-uniform random recursive tree, In and , editors, Random Graphs ’85, volume 33 of Annals of Discrete Mathematics, North Holland, 1987, Amsterdam, pp. 297–306.
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.