Universal rooted phylogenetic tree shapes and universal tanglegrams
| Autor: | Clifton, Ann, Czabarka, Eva, Liu, Kevin, Loeb, Sarah, Okur, Utku, Szekely, Laszlo, Wicke, Kristina |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We provide an $\Omega(n\log n) $ lower bound and an $O(n^2)$ upper bound for the smallest size of rooted binary trees (a.k.a. phylogenetic tree shapes), which are universal for rooted binary trees with $n$ leaves, i.e., contain all of them as induced binary subtrees. We explicitly compute the smallest universal trees for $n\leq 11$. We also provide an $\Omega(n^2) $ lower bound and an $O(n^4)$ upper bound for the smallest size of tanglegrams, which are universal for size $n$ tanglegrams, i.e., which contain all of them as induced subtanglegrams. Some of our results generalize to rooted $d$-ary trees and to $d$-ary tanglegrams. Comment: 18 pages, 14 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|