论文标题
在最大的随机叶子标记二进制树的最大常见子树上的改进的下限
An Improved Lower Bound on the Largest Common Subtree of Random Leaf-Labeled Binary Trees
论文作者
论文摘要
众所周知，有两个独立的随机二进制树的最大公共子树（即最大协议子树）的大小为$ n $给定的标记叶子的订单在$ n^{0.366} $和$ n^{1/2} $之间。我们通过递归地构造一个共同的子树，并证明其渐近生长的下限来改善$ n^{0.4464} $的订单$ n^{0.4464} $。该结构是对D. Aldous提出的算法的修改，通过将树在质心上分裂和递归进行。
It is known that the size of the largest common subtree (i.e., the maximum agreement subtree) of two independent random binary trees with $n$ given labeled leaves is of order between $n^{0.366}$ and $n^{1/2}$. We improve the lower bound to order $n^{0.4464}$ by constructing a common subtree recursively and by proving a lower bound for its asymptotic growth. The construction is a modification of an algorithm proposed by D. Aldous by splitting the tree at the centroid and by proceeding recursively.
