论文标题
插图效果和树木的平均距离
Inset Edges Effect and Average Distance of Trees
论文作者
论文摘要
图表的增加边缘称为插图边缘。预测最小化图平均距离的k插图边缘已知NP-固定。当k = 1时，问题的复杂性是多项式。在本文中，我们进一步找到了一棵树的单个插图边缘（s），其平均距离与给定输入的平均距离最接近。为此，我们可能需要对插图的集合的每个插图边缘的效果。为此，我们提出了一种具有O（M）和O（M/M）之间的时间复杂性和平均值小于O（M.Log（M））的算法，其中M代表可能的插图边缘的数量。然后，最多需要O（log（m））才能在平均距离上找到自定义更改的目标插图。使用理论工具，该算法严格避免在为树上添加新的边缘后，无需重新计算距离而没有更改。然后，使用一些额外技术在[8]中首先引入的一些矩阵工具来降低计算剩余距离的时间复杂性。这使我们具有动态的时间复杂性，并且绝对取决于输入树，该输入树与输入树的Wiener索引成比例。
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. When k = 1 the complexity of the problem is polynomial. In this paper, we further find the single inset edge(s) of a tree with the closest change on the average distance to a given input. To do that we may require the effect of each inset edge for the set of inset edges. For this, we propose an algorithm with the time complexity between O(m) and O(m/m) and an average of less than O( m.log(m)), where m stands for the number of possible inset edges. Then it takes up to O(log(m)) to find the target inset edges for a custom change on the average distance. Using theoretical tools, the algorithm strictly avoids recalculating the distances with no changes, after adding a new edge to a tree. Then reduces the time complexity of calculating remaining distances using some matrix tools which first introduced in [8] with one additional technique. This gives us a dynamic time complexity and absolutely depends on the input tree which is proportion to the Wiener index of the input tree.
