论文标题
独轮车图和直径的直径算法 - 优美的增强树木
Algorithms for Diameters of Unicycle Graphs and Diameter-Optimally Augmenting Trees
论文作者
论文摘要
我们考虑计算独轮车图的直径的问题（即具有独特周期的图）。我们为问题提供了一个O（n）时间算法，其中n是图的顶点。这改善了以前的最佳O（n \ log n）时间解决方案[OH and AHN，ISAAC 2016]。将此算法用作子例程，我们解决了将快捷方式添加到树上的问题，以便将新图的直径（这是独轮图）最小化；我们的算法需要O（n^2 \ log n）时间和o（n）空间。以前的最佳算法解决了O（n^2 \ log^3 n）时间和o（n）空间[OH and Ahn，Isaac 2016]或O（n^2）和O（n^2）和O（n^2）空间[Bilò，Isaac 2018]中的问题。
We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O(n) time algorithm for the problem, where n is the number of vertices of the graph. This improves the previous best O(n \log n) time solution [Oh and Ahn, ISAAC 2016]. Using this algorithm as a subroutine, we solve the problem of adding a shortcut to a tree so that the diameter of the new graph (which is a unicycle graph) is minimized; our algorithm takes O(n^2 \log n) time and O(n) space. The previous best algorithms solve the problem in O(n^2 \log^3 n) time and O(n) space [Oh and Ahn, ISAAC 2016], or in O(n^2) time and O(n^2) space [Bilò, ISAAC 2018].
