Abstract
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees on n leaves have a maximum agreement subtree (MAST) of size at 1 least n2 . In particular, we show that for any c > 0, there exist two balanced rooted binary leaf-labeled trees on n leaves such that any MAST for these two trees has size less than cn2 . We also 1 improve the lower bound of the size of such a MAST to n6 . 1.
Original language | English (US) |
---|---|
Pages (from-to) | 336-354 |
Number of pages | 19 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 36 |
Issue number | 1 |
DOIs | |
State | Published - 2022 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- balanced tree
- catepillar
- maximum agreement subtree
- phylogenetic tree