论文标题
在树上代码
Codes over Trees
论文作者
论文摘要
在图理论中，一棵树是最受欢迎的图形系列之一，在计算机科学以及许多其他相关领域中都有广泛的应用。尽管所有树集都有几个距离的度量，但我们在这里考虑一个定义了所谓的树距离的距离，该距离由最小数量的编辑操作，删除和添加边缘定义，以将一棵树更改为另一棵树。从编码的理论角度来看，在树距离上的代码用于校正边缘擦除和错误。但是，研究此距离度量对于许多其他在其地区使用树木和特性的应用以及邻居树的数量很重要。在此范式下，研究了规定最小树距离的树木上最大的代码。提出了这些代码以及代码构造的上限。我们研究的重要部分致力于计算给定半径的树木球大小的问题。这些球不是规律的，因此我们表明，虽然恒星树具有最小的球尺寸，但对于路径树的最大值是最大的。
In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the path tree.
