English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic datastructure for reporting $(s,t)$ mincuts (and by duality, the values of $(s,t)$maxflows) for all pairs of vertices $s$ and $t$ in an undirected graph. Gomoryand Hu showed that it can be computed using $n-1$ exact maxflow computations.Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50years later, *even for approximate mincuts*. In this paper, we break thislongstanding barrier and give an algorithm for computing a$(1+\epsilon)$-approximate Gomory-Hu tree using $\text{polylog}(n)$ maxflowcomputations. Specifically, we obtain the runtime bounds we describe below.  We obtain a randomized (Monte Carlo) algorithm for undirected, weightedgraphs that runs in $\tilde O(m + n^{3/2})$ time and returns a$(1+\epsilon)$-approximate Gomory-Hu tree algorithm w.h.p. Previously, the bestrunning time known was $\tilde O(n^{5/2})$, which is obtained by running Gomoryand Hu's original algorithm on a cut sparsifier of the graph.  Next, we obtain a randomized (Monte Carlo) algorithm for undirected,unweighted graphs that runs in $m^{4/3+o(1)}$ time and returns a$(1+\epsilon)$-approximate Gomory-Hu tree algorithm w.h.p. This improves on ourfirst result for sparse graphs, namely $m = o(n^{9/8})$. Previously, the bestrunning time known for unweighted graphs was $\tilde O(mn)$ for an exactGomory-Hu tree (Bhalgat et al., STOC 2007); no better result was known ifapproximations are allowed.  As a consequence of our Gomory-Hu tree algorithms, we also solve the$(1+\epsilon)$-approximate all pairs mincut and single source mincut problemsin the same time bounds. (These problems are simpler in that the goal is toonly return the $(s,t)$ mincut values, and not the mincuts.) This improves onthe recent algorithm for these problems in $\tilde O(n^2)$ time due to Abboudet al. (FOCS 2020).

Approximate Gomory-Hu Tree Is Faster Than $n-1$ Max-Flows