Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Label-based parameters in increasing trees

Abstract : Grown simple families of increasing trees are a subclass of increasing trees, which can be constructed by an insertion process. Three such tree families contained in the grown simple families of increasing trees are of particular interest: $\textit{recursive trees}$, $\textit{plane-oriented recursive trees}$ and $\textit{binary increasing trees}$. Here we present a general approach for the analysis of a number of label-based parameters in a random grown simple increasing tree of size $n$ as, e.g., $\textit{the degree of the node labeled j}$, $\textit{the subtree-size of the node labeled j}$, etc. Further we apply the approach to the random variable $X_{n,j,a}$, which counts the number of size-$a$ branches attached to the node labeled $j$ (= subtrees of size $a$ rooted at the children of the node labeled $j$) in a random grown simple increasing tree of size $n$. We can give closed formulæ for the probability distribution and the factorial moments. Furthermore limiting distribution results for $X_{n,j,a}$ are given dependent on the growth behavior of $j=j(n)$ compared to $n$.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184684
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 2:22:58 PM
Last modification on : Wednesday, October 13, 2021 - 7:58:04 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 10:44:30 AM

File

dmAG0123.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Markus Kuba, Alois Panholzer. Label-based parameters in increasing trees. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.321-330, ⟨10.46298/dmtcs.3482⟩. ⟨hal-01184684⟩

Share

Metrics

Record views

34

Files downloads

330