论文标题
难以为困难的树对的有效采样算法
An efficient sampling algorithm for difficult tree pairs
论文作者
论文摘要
是否存在用于计算延长有序二进制树对之间的旋转距离的多项式时间算法，这是一个开放的问题。计算任意树（s，t）之间旋转距离之间的旋转距离的问题可以有效地减小到计算困难的树（S'，t'）之间的旋转距离的问题，那里没有已知的第一步，这可以保证是最小长度路径的开始。因此，有趣的是如何品尝固定尺寸的这类困难对树。我们表明，可以有效地进行此操作，并提出这样的算法，该算法在时间$ o（n^4）$中运行。
It is an open question whether there exists a polynomial-time algorithm for computing the rotation distances between pairs of extended ordered binary trees. The problem of computing the rotation distance between an arbitrary pair of trees, (S, T), can be efficiently reduced to the problem of computing the rotation distance between a difficult pair of trees (S', T'), where there is no known first step which is guaranteed to be the beginning of a minimal length path. Of interest, therefore, is how to sample such difficult pairs of trees of a fixed size. We show that it is possible to do so efficiently, and present such an algorithm that runs in time $O(n^4)$.
