Gomory-Hu tree [Gomory and Hu, 1961] is a succinct representation of pairwise minimum cuts in an undirected graph. When the input graph has general edge weights, classic algorithms need at least cubic running time to compute a Gomory-Hu tree. Very recently, the authors of [AKL+, arXiv v1, 2021] have improved the running time to $\tilde{O}(n^{2.875})$ which breaks the cubic barrier for the first time. In this paper, we refine their approach and improve the running time to $\tilde{O}(n^2)$. This quadratic upper bound is also obtained independently in an updated version by the same group of authors [AKL+, arXiv v2, 2021].
翻译：Gomory-Hu树[Gomory 和 Hu, 1961] 是未定向图形中双向最小剪切的简明表示。 当输入图形具有一般边缘重量时, 经典算法至少需要立方运行时间来计算 Gomory- Hu 树。 最近, [AKL+, arXiv v1, 2021] 的作者将首次打破立方屏障的运行时间提高到 $\ tilde{O} (n ⁇ 2.875}) 。 在本文中, 我们改进了它们的方法, 并将运行时间提高到 $\ tilde{ O} (n ⁇ 2) $ 。 这个四边框的上层也在同一组作者更新版本中独立获得 [AKL+, arXiv v2, 2021] 。
相关内容
微信扫码咨询专知VIP会员