Geodesic
On the number of transversals in random 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 study transversals in random trees with n vertices asymptotically as n tends to infinity. Our investigation treats the average number of transversals of fixed size, the size of a random transversal as well as the probability that a random subset of the vertex set of a tree is a transversal for the class of simply generated trees and for Pólya trees. The last parameter was already studied by Devroye for simply generated trees. We offer an alternative proof based on generating functions and singularity analysis and extend the result to Pólya trees. 
@article{DMTCS_2012_special_262_a11,
     author = {Gittenberger, Bernhard and Kraus, Veronika},
     title = {On the number of transversals in random 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.2990},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2990/}
}
TY  - JOUR
AU  - Gittenberger, Bernhard
AU  - Kraus, Veronika
TI  - On the number of transversals in random 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.2990/
DO  - 10.46298/dmtcs.2990
LA  - en
ID  - DMTCS_2012_special_262_a11
ER  - 
%0 Journal Article
%A Gittenberger, Bernhard
%A Kraus, Veronika
%T On the number of transversals in random 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.2990/
%R 10.46298/dmtcs.2990
%G en
%F DMTCS_2012_special_262_a11
Gittenberger, Bernhard; Kraus, Veronika. On the number of transversals in random 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.2990. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2990/

Cité par Sources :