论文标题
订购：计算Gomory-Hu树的新方法
OrderedCuts: A new approach for computing Gomory-Hu tree
论文作者
论文摘要
Gomory-hu树或割树是一种经典的数据结构，可存储所有对所有节点$（S，T）$的无方向加权图的最低$ S $ -T $切割。我们提出了一种基于对我们称为OrderedCuts的问题的减少来计算切割树的新方法。给定一系列节点$ s，v_1，\ ldots，v_ \ ell $，其目标是计算最小$ \ {s，v_1，\ ldots，v_ {i-1} \} \} $ - $ v_i $ - in [\ ell] $ in [\ ell] $。我们表明，剪切树可以通过$ \ tilde o（1）$呼叫对订购的汇率进行计算。我们还为可能具有独立利益的有序截面建立了新的结果。首先，我们证明所有$ \ ell $ cuts可以用$ o（n）$空间在我们称为OC树的数据结构中进行紧凑。我们定义了这种结构的较弱版本，我们称之为depth-1 oc树，并表明它足以构造切割树。其次，我们证明了允许用于计算OC树的划分算法的结果。我们认为，划分和争议算法的存在使我们的新方法成为实践实施的良好候选人。
The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum $s$-$t$ cuts of an undirected weighted graph for all pairs of nodes $(s,t)$. We propose a new approach for computing the cut tree based on a reduction to the problem that we call OrderedCuts. Given a sequence of nodes $s,v_1,\ldots,v_\ell$, its goal is to compute minimum $\{s,v_1,\ldots,v_{i-1}\}$-$v_i$ cuts for all $i\in[\ell]$. We show that the cut tree can be computed by $\tilde O(1)$ calls to OrderedCuts. We also establish new results for OrderedCuts that may be of independent interest. First, we prove that all $\ell$ cuts can be stored compactly with $O(n)$ space in a data structure that we call an OC tree. We define a weaker version of this structure that we call depth-1 OC tree, and show that it is sufficient for constructing the cut tree. Second, we prove results that allow divide-and-conquer algorithms for computing OC tree. We argue that the existence of divide-and-conquer algorithms makes our new approach a good candidate for a practical implementation.
