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/

Zendy Plus

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

Zendy Tools

Zendy Open

We give an almost-linear time algorithm for the Steiner connectivityaugmentation problem: given an undirected graph, find a smallest (or minimumweight) set of edges whose addition makes a given set of terminals$\tau$-connected (for any given $\tau > 0$). The running time of our algorithmis dominated by polylogarithmic calls to any maximum flow subroutine; using therecent almost-linear time maximum flow algorithm (Chen et al., FOCS 2022), weget an almost-linear running time for our algorithm as well. This is tight upto the polylogarithmic factor even for just two terminals. Prior to our work,an almost-linear (in fact, near-linear) running time was known only for thespecial case of global connectivity augmentation, i.e., when all vertices areterminals (Cen et al., STOC 2022).  We also extend our algorithm to the closely related Steiner splitting-offproblem, where the edges incident on a vertex have to be {\em split-off} whilemaintaining the (Steiner) connectivity of a given set of terminals. Prior toour work, a nearly-linear time algorithm was known only for the special case ofglobal connectivity (Cen et al., STOC 2022). The only known generalizationbeyond global connectivity was to preserve all pairwise connectivities using amuch slower algorithm that makes $n$ calls to an all-pairs maximum flow (orGomory-Hu tree) subroutine (Lau and Yung, SICOMP 2013), as against polylog(n)calls to a (single-pair) maximum flow subroutine in this work.

Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows