[{"doi":"10.1007/3-540-60084-1_81","publication":"22nd International Colloquium on Automata, Languages and Programming","_id":"11806","language":[{"iso":"eng"}],"intvolume":"       944","scopus_import":"1","date_created":"2022-08-11T14:17:33Z","title":"Approximating minimum cuts under insertions","citation":{"apa":"Henzinger, M. H. (1995). Approximating minimum cuts under insertions. In <i>22nd International Colloquium on Automata, Languages and Programming</i> (Vol. 944, pp. 280–291). Szeged, Hungary: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>","short":"M.H. Henzinger, in:, 22nd International Colloquium on Automata, Languages and Programming, Springer Nature, 1995, pp. 280–291.","ieee":"M. H. Henzinger, “Approximating minimum cuts under insertions,” in <i>22nd International Colloquium on Automata, Languages and Programming</i>, Szeged, Hungary, 1995, vol. 944, pp. 280–291.","ama":"Henzinger MH. Approximating minimum cuts under insertions. In: <i>22nd International Colloquium on Automata, Languages and Programming</i>. Vol 944. Springer Nature; 1995:280–291. doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>","chicago":"Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In <i>22nd International Colloquium on Automata, Languages and Programming</i>, 944:280–291. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>.","ista":"Henzinger MH. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.","mla":"Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” <i>22nd International Colloquium on Automata, Languages and Programming</i>, vol. 944, Springer Nature, 1995, pp. 280–291, doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>."},"article_processing_charge":"No","year":"1995","date_updated":"2023-02-14T08:09:08Z","quality_controlled":"1","volume":944,"extern":"1","page":"280–291","status":"public","type":"conference","date_published":"1995-07-01T00:00:00Z","publisher":"Springer Nature","alternative_title":["LNCS"],"abstract":[{"text":"This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε).","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"None","month":"07","publication_identifier":{"eisbn":["9783540600848"],"eissn":["1611-3349"],"isbn":["9783540494256"],"issn":["0302-9743"]},"conference":{"start_date":"1995-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"1995-07-14","location":"Szeged, Hungary"},"publication_status":"published","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"}]}]