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

We give a deterministic algorithm for finding the minimum (weight) cut of anundirected graph on $n$ vertices and $m$ edges using $\text{polylog}(n)$ callsto any maximum flow subroutine. Using the current best deterministic maximumflow algorithms, this yields an overall running time of $\tilde O(m \cdot\min(\sqrt{m}, n^{2/3}))$ for weighted graphs, and $m^{4/3+o(1)}$ forunweighted (multi)-graphs. This marks the first improvement for this problemsince a running time bound of $\tilde O(mn)$ was established by several papersin the early 1990s.  Our global minimum cut algorithm is obtained as a corollary of a minimumSteiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set ofedges whose removal disconnects at least one pair of vertices among adesignated set of terminal vertices. The running time of our deterministicminimum Steiner cut algorithm matches that of the global minimum cut algorithmstated above. Using randomization, the running time improves to $m^{1+o(1)}$because of a faster maximum flow subroutine; this improves the best knownrandomized algorithm for the minimum Steiner cut problem as well.  Our main technical contribution is a new tool that we call *isolating cuts*.Given a set of vertices $R$, this entails finding cuts of minimum weight thatseparate (or isolate) each individual vertex $v\in R$ from the rest of thevertices $R\setminus \{v\}$. Na\"ively, this can be done using $|R|$ maximumflow calls, but we show that just $O(\log |R|)$ suffice for finding isolatingcuts for any set of vertices $R$. We call this the *isolating cut lemma*.

Deterministic Min-cut in Poly-logarithmic Max-flows