Premium
The distribution of the size of the ancestor‐tree and of the induced spanning subtree for random trees
Author(s) -
Panholzer Alois
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20027
Subject(s) - tree (set theory) , combinatorics , mathematics , spanning tree , node (physics) , k ary tree , ancestor , random tree , discrete mathematics , minimum spanning tree , random binary tree , tree structure , computer science , binary tree , physics , archaeology , motion planning , artificial intelligence , robot , history , quantum mechanics
We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor‐tree of p given nodes in a rooted tree T is the subtree of T , spanned by the root and these p nodes and generalizes the depth (ancestor‐tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor‐tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all ( p n ) possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulæ for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulæ for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004