Geodesic
Protected node profile of Tries
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2018_20_1_a11,
     author = {Javanian, Mehri},
     title = {Protected node profile of {Tries}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-12},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-12/}
}
TY  - JOUR
AU  - Javanian, Mehri
TI  - Protected node profile of Tries
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-12/
DO  - 10.23638/DMTCS-20-1-12
LA  - en
ID  - DMTCS_2018_20_1_a11
ER  - 
%0 Journal Article
%A Javanian, Mehri
%T Protected node profile of Tries
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-12/
%R 10.23638/DMTCS-20-1-12
%G en
%F DMTCS_2018_20_1_a11
Javanian, Mehri. Protected node profile of Tries. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-12

Cité par Sources :