论文标题
直径通过度限制来最小化
Diameter Minimization by Shortcutting with Degree Constraints
论文作者
论文摘要
我们考虑将固定数量的新边缘添加到无向图的问题，以最大程度地减少增强图的直径，并且在约束下，每个顶点添加的边数都由整数界定。该问题是由网络设计应用程序激励的，我们希望在没有过多地增加任何单个顶点的程度的情况下最大程度地减少网络中最坏的案例通信，以免额外过载。我们为此任务提供三种算法，每个算法都有自己的优点。匹配增强的特殊情况是，当每个顶点最多可将每个顶点都当成一个新的边缘时，我们都特别感兴趣，为此，我们显示出无Ximimibility的结果，并在将这些边缘添加到路径上时最小可实现的直径的界限。最后，我们在几种不同类型的现实生活网络上进行了经验评估和比较我们的算法。
We consider the problem of adding a fixed number of new edges to an undirected graph in order to minimize the diameter of the augmented graph, and under the constraint that the number of edges added for each vertex is bounded by an integer. The problem is motivated by network-design applications, where we want to minimize the worst case communication in the network without excessively increasing the degree of any single vertex, so as to avoid additional overload. We present three algorithms for this task, each with their own merits. The special case of a matching augmentation, when every vertex can be incident to at most one new edge, is of particular interest, for which we show an inapproximability result, and provide bounds on the smallest achievable diameter when these edges are added to a path. Finally, we empirically evaluate and compare our algorithms on several real-life networks of varying types.
