论文标题
未加权图中Gomory-Hu树的亚皮亚算法
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
论文作者
论文摘要
每个无向图$ g $都有一个（加权）切割的树$ t $，通常以Gomory和Hu的名字命名。 我们给出了第一个为简单的图形$ g $（未加权而没有平行边缘）构建这样的树的亚地铁时算法。它的时间复杂度为$ \ tilde {o}（n^{2.5}）$，对于$ n = | v（g）| $;以前，除了稀疏图之类的受限情况外，只有$ \ tilde {o}（n^3）$。因此，我们在打破立方屏障的简单图中获得了全对最大流的第一种算法。 Gomory和Hu使用$ n-1 $ $ Queries对（单重）Max-Flow计算这棵树；新算法可以将其视为$ \ tilde {o}（\ sqrt {n}）$ max-flow Computations $ n $ node graphs上的细粒度。
Every undirected graph $G$ has a (weighted) cut-equivalent tree $T$, commonly named after Gomory and Hu who discovered it in 1961. Both $T$ and $G$ have the same node set, and for every node pair $s,t$, the minimum $(s,t)$-cut in $T$ is also an exact minimum $(s,t)$-cut in $G$. We give the first subcubic-time algorithm that constructs such a tree for a simple graph $G$ (unweighted with no parallel edges). Its time complexity is $\tilde{O}(n^{2.5})$, for $n=|V(G)|$; previously, only $\tilde{O}(n^3)$ was known, except for restricted cases like sparse graphs. Consequently, we obtain the first algorithm for All-Pairs Max-Flow in simple graphs that breaks the cubic-time barrier. Gomory and Hu compute this tree using $n-1$ queries to (single-pair) Max-Flow; the new algorithm can be viewed as a fine-grained reduction to $\tilde{O}(\sqrt{n})$ Max-Flow computations on $n$-node graphs.
