论文标题
限制旋转距离的分布
Distributions of restricted rotation distances
论文作者
论文摘要
旋转距离测量了有序有序的二进制树之间的结构差异。 Associahedra的一维骨架是旋转图，如果单个旋转与单个旋转不同，则代表树的两个顶点通过边缘连接。没有已知的有效算法来计算树木之间的旋转距离，从而计算旋转图中的距离。限制允许旋转的允许位置会产生许多限制旋转距离的概念。允许在最小的此类位置旋转会产生限制的旋转距离。有线性时间算法来计算受限旋转距离，其中只有两个允许的位置可以发生旋转。相关的限制旋转图具有有效的距离算法。相对于还原树对的尺寸，在限制旋转距离上有线性上限和下限。在这里，我们通过实验研究了以随机选择的大小随机选择的两棵树之间的预期限制旋转距离，并发现它通常位于较早的狭窄带中，在较早的线性上限和下边界内。
Rotation distances measure the differences in structure between rooted ordered binary trees. The one-dimensional skeleta of associahedra are rotation graphs, where two vertices representing trees are connected by an edge if they differ by a single rotation. There are no known efficient algorithms to compute rotation distance between trees and thus distances in rotation graphs. Limiting the allowed locations of where rotations are permitted gives rise to a number of notions of restricted rotation distances. Allowing rotations at a minimal such set of locations gives restricted rotation distance. There are linear-time algorithms to compute restricted rotation distance, where there are only two permitted locations for rotations to occur. The associated restricted rotation graph has an efficient distance algorithm. There are linear upper and lower bounds on restricted rotation distance with respect to the sizes of the reduced tree pairs. Here, we experimentally investigate the expected restricted rotation distance between two trees selected at random of increasing size and find that it lies typically in a narrow band well within the earlier proven linear upper and lower bounds.
