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.
All Science Journal Classification (ASJC) codes
- balanced tree
- maximum agreement subtree
- phylogenetic tree