Protection number in plane trees
Date
2017-10
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Belgrade - School of Electrical Engineering
Abstract
The protection number of a plane tree is the minimal distance of the root
to a leaf; this definition carries over to an arbitrary node in a plane tree by
considering the maximal subtree having this node as a root. We study the the
protection number of a uniformly chosen random tree of size n and also the
protection number of a uniformly chosen node in a uniformly chosen random
tree of size n. The method is to apply singularity analysis to appropriate
generating functions. Additional results are provided as well.
Description
CITATION: Heuberger, C. & Prodinger, H. 2017. Protection number in plane trees. Applicable Analysis and Discrete Mathematics, 11(2):314-326. doi:10.2298/AADM1702314H.
The original publication is available at http://pefmath.etf.rs/home.html
The original publication is available at http://pefmath.etf.rs/home.html
Keywords
Rooted Tree (Mathematics), Tree (Graph theory), Rooted plane trees (Mathematics), Analysis of algorithms
Citation
Heuberger, C. & Prodinger, H. 2017. Protection number in plane trees. Applicable Analysis and Discrete Mathematics, 11(2):314-326. doi:10.2298/AADM1702314H.