Mehri Javanian - Protected node profile of Tries

dmtcs:3744 - Discrete Mathematics & Theoretical Computer Science, March 26, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-12
Protected node profile of TriesArticle

Authors: Mehri Javanian ORCID1

  • 1 University of Zanjan, Zanjan

In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis.


Volume: Vol. 20 no. 1
Section: Analysis of Algorithms
Published on: March 26, 2018
Accepted on: March 6, 2018
Submitted on: June 27, 2017
Keywords: Mellin transform,Generating func- tions,Generating func tions,Poissonization,tries,protected nodes,tree profiles,recurrences,generating functions,singularity analysis,saddle point method,[MATH]Mathematics [math],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Horizon21: Early language development in Down Syndrome; Code: PTDC/MHC-LIN/3901/2014

Consultation statistics

This page has been seen 450 times.
This article's PDF has been downloaded 393 times.