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 the first almost-linear time algorithm for computing the\emph{maximal $k$-edge-connected subgraphs} of an undirected unweighted graphfor any constant $k$. More specifically, given an $n$-vertex $m$-edge graph$G=(V,E)$ and a number $k = \log^{o(1)}n$, we can deterministically compute in$O(m+n^{1+o(1)})$ time the unique vertex partition $\{V_{1},\dots,V_{z}\}$ suchthat, for every $i$, $V_{i}$ induces a $k$-edge-connected subgraph while everysuperset $V'_{i}\supset V_{i}$ does not. Previous algorithms with linear timework only when $k\le2$ {[}Tarjan SICOMP'72{]}, otherwise they all require$\Omega(m+n\sqrt{n})$ time even when $k=3$ {[}Chechik~et~al.~SODA'17;Forster~et~al.~SODA'20{]}.  Our algorithm also extends to the decremental graph setting; we candeterministically maintain the maximal $k$-edge-connected subgraphs of a graphundergoing edge deletions in $m^{1+o(1)}$ total update time. Our key idea is areduction to the dynamic algorithm supporting pairwise $k$-edge-connectivityqueries {[}Jin and Sun FOCS'20{]}.

Maximal $k$-Edge-Connected Subgraphs in Almost-Linear Time for Small $k$