Back to Search
Start Over
On the maximum agreement subtree conjecture for balanced trees
- Publication Year :
- 2020
-
Abstract
- We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on $n$ leaves have a maximum agreement subtree (MAST) of size at least $n^{\frac{1}{2}}$. In particular, we show that for any $c>0$, there exist two balanced rooted binary leaf-labelled trees on $n$ leaves such that any MAST for these two trees has size less than $c n^{\frac{1}{2}}$. We also improve the lower bound of the size of such a MAST to $n^{\frac{1}{6}}$.
- Subjects :
- Mathematics - Combinatorics
Quantitative Biology - Populations and Evolution
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2005.07357
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/20M1379678