{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:20:33Z","timestamp":1767853233848,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["160364472"],"award-info":[{"award-number":["160364472"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s00453-022-00978-0","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T05:05:32Z","timestamp":1653541532000},"page":"2702-2734","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Mincut Sensitivity Data Structures for the Insertion of an Edge"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8657-7182","authenticated-orcid":false,"given":"Surender","family":"Baswana","sequence":"first","affiliation":[]},{"given":"Shiv","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Till","family":"Knollmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"978_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Krauthgamer, R., Trabelsi, O.: Subcubic algorithms for Gomory\u2013Hu tree in unweighted graphs. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, pp. 1725\u20131737. ACM (2021). https:\/\/doi.org\/10.1145\/3406325.3451073","DOI":"10.1145\/3406325.3451073"},{"issue":"2","key":"978_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131\u2013137 (1972). https:\/\/doi.org\/10.1137\/0201008","journal-title":"SIAM J. Comput."},{"key":"978_CR3","volume-title":"Network Flows\u2013Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows\u2013Theory, Algorithms and Applications. Prentice Hall, Hoboken (1993)"},{"issue":"3","key":"978_CR4","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1007\/s00453-018-0452-3","volume":"81","author":"S Baswana","year":"2019","unstructured":"Baswana, S., Choudhary, K., Roditty, L.: An efficient strongly connected components algorithm in the fault tolerant model. Algorithmica 81(3), 967\u2013985 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0452-3","journal-title":"Algorithmica"},{"key":"978_CR5","doi-asserted-by":"publisher","unstructured":"Baswana, S., Gupta, S.K., Tulsyan, A.: Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26\u201330, 2019, Aachen, Germany, LIPIcs, vol. 138, p. 65:1-65:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.65","DOI":"10.4230\/LIPIcs.MFCS.2019.65"},{"key":"978_CR6","doi-asserted-by":"crossref","unstructured":"Baswana, S., Pandey, A.: Sensitivity oracles for all-pairs mincuts. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 581\u2013609. SIAM (2022)","DOI":"10.1137\/1.9781611977073.27"},{"issue":"1","key":"978_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5\u201312 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2003.05.002","journal-title":"Theor. Comput. Sci."},{"key":"978_CR8","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Karger, D.R.: A nearly optimal oracle for avoiding failed vertices and edges. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2, 2009, pp. 101\u2013110. ACM (2009). https:\/\/doi.org\/10.1145\/1536414.1536431","DOI":"10.1145\/1536414.1536431"},{"key":"978_CR9","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2015.02.036","volume":"580","author":"G Braunschvig","year":"2015","unstructured":"Braunschvig, G., Chechik, S., Peleg, D., Sealfon, A.: Fault tolerant additive and ($$\\mu $$, $$\\alpha $$)-spanners. Theor. Comput. Sci. 580, 94\u2013100 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.02.036","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"978_CR10","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/090751670","volume":"40","author":"TM Chan","year":"2011","unstructured":"Chan, T.M., Patrascu, M., Roditty, L.: Dynamic connectivity: connecting to networks and geometry. SIAM J. Comput. 40(2), 333\u2013349 (2011). https:\/\/doi.org\/10.1137\/090751670","journal-title":"SIAM J. Comput."},{"key":"978_CR11","doi-asserted-by":"publisher","unstructured":"Chechik, S., Cohen, S.: Distance sensitivity oracles with subcubic preprocessing time and fast query time. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22\u201326, 2020, pp. 1375\u20131388. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384253","DOI":"10.1145\/3357713.3384253"},{"issue":"7","key":"978_CR12","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1137\/090758039","volume":"39","author":"S Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault tolerant spanners for general graphs. SIAM J. Comput. 39(7), 3403\u20133423 (2010). https:\/\/doi.org\/10.1137\/090758039","journal-title":"SIAM J. Comput."},{"key":"978_CR13","doi-asserted-by":"publisher","unstructured":"Chen, L., Goranci, G., Henzinger, M., Peng, R., Saranurak, T.: Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 1135\u20131146. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00109","DOI":"10.1109\/FOCS46700.2020.00109"},{"key":"978_CR14","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Kamma, L., Krauthgamer, R.: Tight bounds for Gomory\u2013Hu-like cut counting. In: Graph-Theoretic Concepts in Computer Science\u201442nd International Workshop, WG 2016, Istanbul, Turkey, June 22\u201324, 2016, Revised Selected Papers, pp. 133\u2013144 (2016). https:\/\/doi.org\/10.1007\/978-3-662-53536-3_12","DOI":"10.1007\/978-3-662-53536-3_12"},{"issue":"5","key":"978_CR15","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput. 37(5), 1299\u20131318 (2008). https:\/\/doi.org\/10.1137\/S0097539705429847","journal-title":"SIAM J. Comput."},{"issue":"3","key":"978_CR16","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1137\/S0097539797330045","volume":"30","author":"Y Dinitz","year":"2000","unstructured":"Dinitz, Y., Vainshtein, A.: The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. Odd case. SIAM J. Comput. 30(3), 753\u2013808 (2000). https:\/\/doi.org\/10.1137\/S0097539797330045","journal-title":"SIAM J. Comput."},{"key":"978_CR17","doi-asserted-by":"publisher","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for graphs subject to vertex failures. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 490\u2013509. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.31","DOI":"10.1137\/1.9781611974782.31"},{"key":"978_CR18","unstructured":"Dinits, E.A, Lomonosov, M.: On the structure of a family of minimum weighted cuts in a graph. In: Studies in Discrete Optimizations (1976). http:\/\/alexander-karzanov.net\/ScannedOld\/76_cactus_transl.pdf"},{"key":"978_CR19","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Can. J. Math."},{"issue":"1","key":"978_CR20","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s004530010032","volume":"28","author":"D Frigioni","year":"2000","unstructured":"Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica 28(1), 76\u2013103 (2000). https:\/\/doi.org\/10.1007\/s004530010032","journal-title":"Algorithmica"},{"issue":"4","key":"978_CR21","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"2","key":"978_CR22","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3174803","volume":"14","author":"G Goranci","year":"2018","unstructured":"Goranci, G., Henzinger, M., Thorup, M.: Incremental exact min-cut in polylogarithmic amortized update time. ACM Trans. Algorithms 14(2), 17:1-17:21 (2018). https:\/\/doi.org\/10.1145\/3174803","journal-title":"ACM Trans. Algorithms"},{"key":"978_CR23","doi-asserted-by":"publisher","unstructured":"Goranci, G., R\u00e4cke, H., Saranurak, T., Tan, Z.: The expander hierarchy and its applications to dynamic graph algorithms. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 2212\u20132228. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.132","DOI":"10.1137\/1.9781611976465.132"},{"issue":"2","key":"978_CR24","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1111\/j.2517-6161.1989.tb01764.x","volume":"51","author":"DM Greig","year":"1989","unstructured":"Greig, D.M., Porteous, B.T., Seheult, A.H.: Exact maximum a posteriori estimation for binary images. J. R. Stat. Soc. Ser. B (Methodol.) 51(2), 271\u2013279 (1989)","journal-title":"J. R. Stat. Soc. Ser. B (Methodol.)"},{"issue":"1","key":"978_CR25","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0219009","volume":"19","author":"D Gusfield","year":"1990","unstructured":"Gusfield, D.: Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19(1), 143\u2013155 (1990). https:\/\/doi.org\/10.1137\/0219009","journal-title":"SIAM J. Comput."},{"key":"978_CR26","doi-asserted-by":"publisher","unstructured":"Hariharan, R., Kavitha, T., Panigrahi, D., Bhalgat, A.: An $$\\tilde{O}$$(mn) Gomory\u2013Hu tree construction algorithm for unweighted graphs. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007, pp. 605\u2013614 (2007). https:\/\/doi.org\/10.1145\/1250790.1250879. See also the extended version at http:\/\/hariharan-ramesh.com\/papers\/gohu.pdf","DOI":"10.1145\/1250790.1250879"},{"key":"978_CR27","doi-asserted-by":"publisher","unstructured":"Hartmann, T., Wagner, D.: Fast and simple fully-dynamic cut tree construction. In: Algorithms and Computation\u201423rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19\u201321, 2012. Proceedings, pp. 95\u2013105 (2012). https:\/\/doi.org\/10.1007\/978-3-642-35261-4_13","DOI":"10.1007\/978-3-642-35261-4_13"},{"issue":"2","key":"978_CR28","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147\u2013159 (2004). https:\/\/doi.org\/10.1109\/TPAMI.2004.1262177","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"978_CR29","doi-asserted-by":"publisher","unstructured":"Li, J., Panigrahi, D., Saranurak, T.: A nearly optimal all-pairs min-cuts algorithm in simple graphs. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7\u201310, 2022, pp. 1124\u20131134. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00111","DOI":"10.1109\/FOCS52979.2021.00111"},{"key":"978_CR30","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"M Padberg","year":"1990","unstructured":"Padberg, M., Rinaldi, G.: Facet identification for the symmetric traveling salesman polytope. Math. Program. 47, 219\u2013257 (1990). https:\/\/doi.org\/10.1007\/BF01580861","journal-title":"Math. Program."},{"issue":"1","key":"978_CR31","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2976741","volume":"13","author":"M Parter","year":"2016","unstructured":"Parter, M., Peleg, D.: Sparse fault-tolerant BFS structures. ACM Trans. Algorithms 13(1), 11:1-11\"24 (2016). https:\/\/doi.org\/10.1145\/2976741","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"978_CR32","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/3022730","volume":"14","author":"M Parter","year":"2018","unstructured":"Parter, M., Peleg, D.: Fault-tolerant approximate BFS structures. ACM Trans. Algorithms 14(1), 10:1-10:15 (2018). https:\/\/doi.org\/10.1145\/3022730","journal-title":"ACM Trans. Algorithms"},{"key":"978_CR33","doi-asserted-by":"publisher","unstructured":"Picard, J., Queyranne, M.: On the structure of all minimum cuts in a network and applications. In: Rayward-Smith V.J. (ed.) Combinatorial Optimization II. Mathematical Programming Studies, vol. 13(1), pp. 8\u201316 (1980). https:\/\/doi.org\/10.1007\/BFb0120902","DOI":"10.1007\/BFb0120902"},{"issue":"3","key":"978_CR34","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"978_CR35","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00493-007-0045-2","volume":"27","author":"M Thorup","year":"2007","unstructured":"Thorup, M.: Fully-dynamic min-cut. Combinatorica 27(1), 91\u2013127 (2007). https:\/\/doi.org\/10.1007\/s00493-007-0045-2","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00978-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00978-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00978-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T22:32:29Z","timestamp":1727303549000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00978-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":35,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["978"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00978-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"5 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}