{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:05Z","timestamp":1781078225325,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":85,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1086\/18"],"award-info":[{"award-number":["1086\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451073","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1725-1737","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Subcubic algorithms for Gomory\u2013Hu tree in unweighted graphs"],"prefix":"10.1145","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Trabelsi","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00019"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050987"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0089"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397504"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0961"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.76"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.05.003"},{"key":"e_1_3_2_1_13_1","volume-title":"28th Annual European Symposium on Algorithms (ESA","author":"Baswana Surender","year":"2020","unstructured":"Surender Baswana, Shiv Gupta, and Till Knollmann. 2020. Mincut Sensitivity Data Structures for the Insertion of an Edge. In 28th Annual European Symposium on Algorithms (ESA 2020)."},{"key":"e_1_3_2_1_14_1","volume-title":"Efficient Algorithms for Steiner Edge Connectivity Computationand Gomory-Hu Tree Construction for Unweighted Graphs","author":"Bhalgat Anand","year":"2008","unstructured":"Anand Bhalgat, Richard Cole, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2008. Efficient Algorithms for Steiner Edge Connectivity Computationand Gomory-Hu Tree Construction for Unweighted Graphs. 2008. http:\/\/hariharan-ramesh.com\/papers\/gohu.pdf"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250879"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2016.22"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684068"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344424"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.16"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/110844970"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53536-3_12"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780568"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"e_1_3_2_1_28_1","volume-title":"Submodular functions, matroids, and certain polyhedra. Combinatorial structures and their applications","author":"Edmonds Jack","year":"1970","unstructured":"Jack Edmonds. 1970. Submodular functions, matroids, and certain polyhedra. Combinatorial structures and their applications, 1970. Pages 69\u201387."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0161"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.5.680"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185453"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.57"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1136"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90079-X"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219009"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 127\u2013136","author":"Hariharan Ramesh","year":"2007","unstructured":"Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2007. Efficient algorithms for computing all low s-t edge connectivities and related problems. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 127\u2013136. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283398"},{"key":"e_1_3_2_1_42_1","volume-title":"Dynamic Gomory\u2013Hu Tree Construction\u2013fast and simple. arXiv preprint arXiv:1310.0178","author":"Hartmann Tanja","year":"2013","unstructured":"Tanja Hartmann and Dorothea Wagner. 2013. Dynamic Gomory\u2013Hu Tree Construction\u2013fast and simple. arXiv preprint arXiv:1310.0178, 2013."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196312334"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.4.535"},{"key":"e_1_3_2_1_45_1","volume-title":"An algorithm for computing maximum solution bases. Operations research letters, 9, 5","author":"Hassin Rafael","year":"1990","unstructured":"Rafael Hassin. 1990. An algorithm for computing maximum solution bases. Operations research letters, 9, 5, 1990. Pages 315\u2013318."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02115756"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.08.012"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1180335"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/070705994"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274663"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21708-5"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212510"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.66"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00017"},{"key":"e_1_3_2_1_62_1","volume-title":"Liu and Aaron Sidford","author":"Yang","year":"2019","unstructured":"Yang P. Liu and Aaron Sidford. 2019. Faster Energy Maximization for Faster Maximum Flow. CoRR, 2019. arxiv:1910.14276"},{"key":"e_1_3_2_1_63_1","volume-title":"Liu and Aaron Sidford","author":"Yang","year":"2020","unstructured":"Yang P. Liu and Aaron Sidford. 2020. Unit Capacity Maxflow in Almost m^4\/3 Time. CoRR, abs\/2003.08929, 2020. arxiv:2003.08929"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_69_1","volume-title":"CoRR, 2018","author":"Naves Guyslain","year":"2018","unstructured":"Guyslain Naves and F Bruce Shepherd. 2018. When Do Gomory-Hu Subtrees Exist? CoRR, 2018. arxiv:1807.07331"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.42"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_168"},{"key":"e_1_3_2_1_74_1","volume-title":"On the structure of all minimum cuts in a network and applications","author":"Picard Jean-Claude","unstructured":"Jean-Claude Picard and Maurice Queyranne. 1980. On the structure of all minimum cuts in a network and applications. In Combinatorial Optimization II. Springer. Pages 8\u201316."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.17"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.9"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1078"},{"key":"e_1_3_2_1_80_1","series-title":"SIAM Journal on computing, 42, 1","volume-title":"A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning","author":"Spielman Daniel A","year":"2013","unstructured":"Daniel A Spielman and Shang-Hua Teng. 2013. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, 42, 1, 2013. Pages 1\u201326."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_82_1","volume-title":"Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.","author":"van den Brand Jan","year":"2021","unstructured":"Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2021. Minimum Cost Flows, MDPs, and \\ell _1-Regression in Nearly Linear Time for Dense Instances. CoRR, 2021. arxiv:2101.05719"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_84_1","volume-title":"An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation","author":"Wu Zhenyu","year":"1993","unstructured":"Zhenyu Wu and Richard Leahy. 1993. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE transactions on pattern analysis and machine intelligence, 15, 11, 1993. Pages 1101\u20131113."},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.006"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451073","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":85,"alternative-id":["10.1145\/3406325.3451073","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451073","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}