๐ฎ
๐ฎ
The Ethereal
Reticulation-visible networks
August 21, 2015 ยท The Ethereal ยท ๐ Advances in Applied Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Magnus Bordewich, Charles Semple
arXiv ID
1508.05424
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
33
Venue
Advances in Applied Mathematics
Last Checked
1 month ago
Abstract
Let $X$ be a finite set, $\mathcal N$ be a reticulation-visible network on $X$, and $\mathcal T$ be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not $\mathcal N$ displays $\mathcal T$. Furthermore, for all $|X|\ge 1$, we show that $\mathcal N$ has at most $8|X|-7$ vertices in total and at most $3|X|-3$ reticulation vertices, and that these upper bounds are sharp.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal