论文标题
关于插图边缘和树木平均距离的一些初步结果
Some Preliminary Result About the Inset Edge and Average Distance of Trees
论文作者
论文摘要
图表的增加边缘称为插图边缘。预测最小化图平均距离的k插图边缘已知NP-固定。但是，当k = 1时，问题的复杂性是多项式。在本文中，建立了一些对树木问题进行精确分析的工具。使用工具，我们可以避免使用距离矩阵。这导致了更有效的算法和对问题的更好分析。呈现在树上插入插图时，工具的几种应用以及紧密的限制，以改变平均距离。
An added edge to a graph is called an inset edge. Predicting k inset edges which minimize the average distance of a graph is known to be NP-Hard. However, when k = 1 the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the problem for the trees are established. Using the tools, we can avoid using the distance matrix. This leads to more efficient algorithms and a better analysis of the problem. Several applications of the tools as well as a tight bound for the change of average distance when an inset edge is added to a tree are presented.
