Geodesic
On trees, tanglegrams, and tangled chains
Discrete mathematics & theoretical computer science, DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016) (2020).

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

Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared. 
@article{DMTCS_2020_special_379_a30,
     author = {Billey, Sara and Konvalinka, Matjaz and Matsen IV, Frderick},
     title = {On trees, tanglegrams, and tangled chains},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)},
     year = {2020},
     doi = {10.46298/dmtcs.6348},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6348/}
}
TY  - JOUR
AU  - Billey, Sara
AU  - Konvalinka, Matjaz
AU  - Matsen IV, Frderick
TI  - On trees, tanglegrams, and tangled chains
JO  - Discrete mathematics & theoretical computer science
PY  - 2020
VL  - DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6348/
DO  - 10.46298/dmtcs.6348
LA  - en
ID  - DMTCS_2020_special_379_a30
ER  - 
%0 Journal Article
%A Billey, Sara
%A Konvalinka, Matjaz
%A Matsen IV, Frderick
%T On trees, tanglegrams, and tangled chains
%J Discrete mathematics & theoretical computer science
%D 2020
%V DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6348/
%R 10.46298/dmtcs.6348
%G en
%F DMTCS_2020_special_379_a30
Billey, Sara; Konvalinka, Matjaz; Matsen IV, Frderick. On trees, tanglegrams, and tangled chains. Discrete mathematics & theoretical computer science, DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016) (2020). doi : 10.46298/dmtcs.6348. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6348/

Cité par Sources :