ON THE MAXIMUM AGREEMENT SUBTREE CONJECTURE FOR BALANCED TREES
ON THE MAXIMUM AGREEMENT SUBTREE CONJECTURE FOR BALANCED TREES
复制标题
DOI：
10.1137/20m1379678
复制
发表时间：
2022-01-01
影响因子：
0.8
通讯作者：
Wicke，Kristina
中科院分区：
文献类型：
--
作者：
Bordewich，Magnus;Linz，Simone;Wicke，Kristina
本文对Martin和Thatte关于两棵平衡的根二叉树在叶子上有最大一致子树的猜想给出了一个反例。特别是，我们证明了，对于任何，存在两个平衡的有根二元叶标记树onleaves，使这两棵树的任何MAST的大小小于。我们还提高了这样的MAST的大小的下界。
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees onleaves have a maximum agreement subtree (MAST) of size at least. In particular, we show that for any, there exist two balanced rooted binary leaf-labeled trees onleaves such that any MAST for these two trees has size less than. We also improve the lower bound of the size of such a MAST to.