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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present a deterministic incremental algorithm for \textit{exactly}maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized timeper edge insertion and $O(1)$ query time. This result partially answers an openquestion posed by Thorup [Combinatorica 2007]. It also stays in sharp contrastto a polynomial conditional lower-bound for the fully-dynamic weighted minimumcut problem. Our algorithm is obtained by combining a recent sparsificationtechnique of Kawarabayashi and Thorup [STOC 2015] and an exact incrementalalgorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficientincremental algorithms for the minimum cut problem. Concretely, we show thatthere exists an ${O}(n\log n/\varepsilon^2)$ space Monte-Carlo algorithm thatcan process a stream of edge insertions starting from an empty graph, and withhigh probability, the algorithm maintains a $(1+\varepsilon)$-approximation tothe minimum cut. The algorithm has $\widetilde{O}(1)$ amortized update-time andconstant query-time.

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time