×

Depth of nodes in random recursive \(k\)-ary trees. (English) Zbl 1187.68347

Summary: We find the expected degree of each node in random recursive \(k\)-ary trees. The expression found for the expected value is used to determine the exact distribution of the depth of \(n\)-th node. It is further shown that the limiting distribution of the normalized depth of this node is a standard normal distribution.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balińska, K. T.; Quintas, L. V., The sequential generation of random \(f\)-graphs. Line maximal 2-, 3-, and 4-graphs, Comput. Chemistry, 14, 323-328 (1990)
[2] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3] Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, (CAAP ’92 (Rennes, 1992). CAAP ’92 (Rennes, 1992), Lecture Notes in Comput. Sci., vol. 581 (1992), Springer: Springer Berlin), 24-48
[4] H. Galina, Szustalewicz, A kinetic theory of stepwise crosslinking polymerization with substitution effect, Macromolecules 22, 3124-3129; H. Galina, Szustalewicz, A kinetic theory of stepwise crosslinking polymerization with substitution effect, Macromolecules 22, 3124-3129
[5] Hogg, R. V.; Craig, A. T., Introduction to Mathematical Statistics (1970), Macmillan Publishing Co., Inc.: Macmillan Publishing Co., Inc. New York · Zbl 0192.25603
[6] Janson, S., Asymptotic degree distribution in random recursive trees, Random Structures Algorithms, 26, 2, 69-83 (2005) · Zbl 1059.05094
[7] Prodinger, H., Depth and path length of heap ordered trees, Internat. J. Found. Comput. Sci., 7, 293-299 (1996) · Zbl 0859.68069
[8] Quintas, L. V.; Szymanski, J., Nonuniform random recursive trees with bounded degree, (Sets, Graphs and Numbers. Sets, Graphs and Numbers, Colloq. Math. Soc. Janos Bolyai, vol. 60 (1991), Academiai Kiado: Academiai Kiado Budapest), 611-620 · Zbl 0788.05025
[9] Smythe, R.; Mahmoud, H., A survey of recursive trees, Theory Probab. Math. Statist., 51, 1-29 (1996) · Zbl 0933.05038
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.