2026-07-20T11:45:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6358 2024-03-06T10:38:09Z ddc:004 open_access

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time Goranci, Gramoz Henzinger, Monika Thorup, Mikkel Dynamic Graph Algorithms Minimum Cut Edge Connectivity We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with ~O(1) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(n log n/epsilon^2) space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+epsilon)-approximation to the minimum cut. The algorithm has ~O(1) amortized update-time and constant query-time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gramoz Goranci and Monika Henzinger and Mikkel Thorup 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.46 urn:nbn:de:0030-drops-63584 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.46 eng https://creativecommons.org/licenses/by/3.0/legalcode