论文标题
Gomory-Hu建筑树算法的计算研究
A computational study of Gomory-Hu construction tree algorithms
论文作者
论文摘要
本文研究了用于计算Gomory-Hu树的算法，该算法是一种经典的数据结构，可将所有最低$ s $ -s $ -t $ t $ cuts存储在无方向的加权图中。我们考虑了两类算法：Gomory和Hu的原始方法，以及我们最近提出的基于“有序曲线”的方法。我们描述了这些方法的实际实现，并将它们与Goldberg和Tsioutsiouliklis（2001）和Akibo等人的实验研究的算法进行了实验比较。 （2016年）（专为未加权简单图表而设计）。结果表明，基于订购的方法是最强大的方法，并且通常以很大的因素优于其他实现。
This paper studies algorithms for computing a Gomory-Hu tree, which is a classical data structure that compactly stores all minimum $s$-$t$ cuts of an undirected weighted graph. We consider two classes of algorithms: the original method by Gomory and Hu and the method based on "OrderedCuts" that we recently proposed. We describe practical implementations of these methods, and compare them experimentally with the algorithms from the previous experimental studies by Goldberg and Tsioutsiouliklis (2001) and by Akibo et al. (2016) (designed for unweighted simple graphs). Results indicate that the method based on OrderedCuts is the most robust, and often outperforms other implementations by a large factor.
