Geodesic
On the Number of 2-Protected Nodes in Tries and Suffix Trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

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

We use probabilistic and combinatorial tools on strings to discover the average number of 2-protected nodes in tries and in suffix trees. Our analysis covers both the uniform and non-uniform cases. For instance, in a uniform trie with $n$ leaves, the number of 2-protected nodes is approximately 0.803$n$, plus small first-order fluctuations. The 2-protected nodes are an emerging way to distinguish the interior of a tree from the fringe. 
@article{DMTCS_2012_special_262_a29,
     author = {Gaither, Jeffrey and Homma, Yushi and Sellke, Mark and Ward, Mark Daniel},
     title = {On the {Number} of {2-Protected} {Nodes} in {Tries} and {Suffix} {Trees}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.3008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3008/}
}
TY  - JOUR
AU  - Gaither, Jeffrey
AU  - Homma, Yushi
AU  - Sellke, Mark
AU  - Ward, Mark Daniel
TI  - On the Number of 2-Protected Nodes in Tries and Suffix Trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3008/
DO  - 10.46298/dmtcs.3008
LA  - en
ID  - DMTCS_2012_special_262_a29
ER  - 
%0 Journal Article
%A Gaither, Jeffrey
%A Homma, Yushi
%A Sellke, Mark
%A Ward, Mark Daniel
%T On the Number of 2-Protected Nodes in Tries and Suffix Trees
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3008/
%R 10.46298/dmtcs.3008
%G en
%F DMTCS_2012_special_262_a29
Gaither, Jeffrey; Homma, Yushi; Sellke, Mark; Ward, Mark Daniel. On the Number of 2-Protected Nodes in Tries and Suffix Trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.3008. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3008/

Cité par Sources :