论文标题
有效计算定向的最小跨树
Efficiently Computing Directed Minimum Spanning Trees
论文作者
论文摘要
计算一个名为Arborescence的定向最小跨越树是一个基本算法问题，尽管不像其无向对应物那样常见。 1967年，埃德蒙兹（Edmonds）讨论了一种优雅的解决方案。它的精制以$ o（\ min（n^2，m \ log n））$运行，tarjan对于非常密集且非常稀疏的图是最佳的。 Gabow等人给出了Edmonds的算法版本，该算法以$ O（N \ log n + M）$运行，因此在稀疏和密集之间的制度中渐近地击败了Tarjan变体。尽管关注问题从理论上讲，但据我们所知，仍然存在对这两种算法的经验评估。实际上，Gabow等人的版本从未实施过，除了编码竞赛外，所有容易获得的Tarjan实现都以$ O（n^2）$运行。在本文中，我们提供了Gabow等人的第一个版本的实现，以及Tarjan版本的五种具有不同基础数据结构的变体。我们在大量的现实世界和随机图上评估了这些算法和现有求解器。
Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in $O(\min(n^2, m\log n))$ by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al.~gave a version of Edmonds' algorithm that runs in $O(n\log n + m)$, thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al.~has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in $O(n^2)$. In this paper, we provide the first implementation of the version by Gabow et al.~as well as five variants of Tarjan's version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.
