{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:53Z","timestamp":1781077553260,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519945","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"151-161","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimal vertex connectivity oracles"],"prefix":"10.1145","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Longhui","family":"Yin","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00019"},{"key":"#cr-split#-e_1_3_2_1_3_1.1","unstructured":"Amir Abboud Robert Krauthgamer and Ohad Trabelsi. 2021. APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. Accepted to FOCS'21 https:\/\/doi.org\/10.48550\/ARXIV.2106.02981 arXiv:2106.02981 10.48550\/ARXIV.2106.02981"},{"key":"#cr-split#-e_1_3_2_1_3_1.2","unstructured":"Amir Abboud Robert Krauthgamer and Ohad Trabelsi. 2021. APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. Accepted to FOCS'21 https:\/\/doi.org\/10.48550\/ARXIV.2106.02981 arXiv:2106.02981"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01961541"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236730"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492466"},{"key":"e_1_3_2_1_7_1","volume-title":"Gr\u00f6tschel and G. O. H. Katona (Eds.) (Bolyai Society Mathematical Studies","volume":"135","author":"Bencz\u00far A. A.","unstructured":"A. A. Bencz\u00far and M. X. Goemans . 2008. Deformable polygon representation and near-mincuts. In Building Bridges: Between Mathematics and Computer Science, M . Gr\u00f6tschel and G. O. H. Katona (Eds.) (Bolyai Society Mathematical Studies , Vol. 19). Springer, 103\u2013 135 . A. A. Bencz\u00far and M. X. Goemans. 2008. Deformable polygon representation and near-mincuts. In Building Bridges: Between Mathematics and Computer Science, M. Gr\u00f6tschel and G. O. H. Katona (Eds.) (Bolyai Society Mathematical Studies, Vol. 19). Springer, 103\u2013135."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840366"},{"key":"e_1_3_2_1_10_1","unstructured":"Chandra Chekuri. 2015. Some open problems in element connectivity. Unpublished Survey. Available at http:\/\/chekuri. cs. illinois. edu\/papers\/elem-connectivity-open-probs. pdf  Chandra Chekuri. 2015. Some open problems in element connectivity. Unpublished Survey. Available at http:\/\/chekuri. cs. illinois. edu\/papers\/elem-connectivity-open-probs. pdf"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_27"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02115755"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/110844970"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a018"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC). 194\u2013200","author":"Cohen Robert F","year":"1993","unstructured":"Robert F Cohen , Giuseppe Di Battista , Arkady Kanevsky , and Roberto Tamassia . 1993 . Reinventing the wheel: an optimal data structure for connectivity queries (extended abstract) . In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC). 194\u2013200 . Robert F Cohen, Giuseppe Di Battista, Arkady Kanevsky, and Roberto Tamassia. 1993. Reinventing the wheel: an optimal data structure for connectivity queries (extended abstract). In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC). 194\u2013200."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_29"},{"key":"e_1_3_2_1_17_1","unstructured":"E. A. Dinic A. V. Karzanov and M. V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimization 290\u2013306. (in Russian)  E. A. Dinic A. V. Karzanov and M. V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimization 290\u2013306. (in Russian)"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings 27th ACM Symposium on Theory of Computing (STOC). 509\u2013518","author":"Dinitz Y.","unstructured":"Y. Dinitz and Z. Nutov . 1995. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance . In Proceedings 27th ACM Symposium on Theory of Computing (STOC). 509\u2013518 . Y. Dinitz and Z. Nutov. 1995. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In Proceedings 27th ACM Symposium on Theory of Computing (STOC). 509\u2013518."},{"key":"e_1_3_2_1_19_1","unstructured":"Y. Dinitz and Z. Nutov. 1999. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part I: the odd case. Unpublished manuscript  Y. Dinitz and Z. Nutov. 1999. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part I: the odd case. Unpublished manuscript"},{"key":"e_1_3_2_1_20_1","unstructured":"Y. Dinitz and Z. Nutov. 1999. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part II: the even case. Unpublished manuscript  Y. Dinitz and Z. Nutov. 1999. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Part II: the even case. Unpublished manuscript"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195442"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 302\u2013311","author":"Dinitz Yefim","year":"1995","unstructured":"Yefim Dinitz and Alek Vainshtein . 1995 . Locally Orientable Graphs, Cell Structures, and a New Algorithm for the Incremental Maintenance of Connectivity Carcasses . In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 302\u2013311 . http:\/\/dl.acm.org\/citation.cfm?id=313651.313711 Yefim Dinitz and Alek Vainshtein. 1995. Locally Orientable Graphs, Cell Structures, and a New Algorithm for the Incremental Maintenance of Connectivity Carcasses. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 302\u2013311. http:\/\/dl.acm.org\/citation.cfm?id=313651.313711"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797330045"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00023-1"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9991-z"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.126"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170302"},{"key":"e_1_3_2_1_28_1","volume-title":"Introduction to Random Graphs","author":"Frieze Alan","unstructured":"Alan Frieze and Micha\u0142 Karo\u0144ski . 2016. Introduction to Random Graphs . Cambridge University Press . Alan Frieze and Micha\u0142 Karo\u0144ski. 2016. Introduction to Random Graphs. Cambridge University Press."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.57"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.8"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.007"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"R. E. Gomory and T. C. Hu. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9 (1961).  R. E. Gomory and T. C. Hu. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9 (1961).","DOI":"10.1137\/0109047"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings First ACM-SIAM Symposium on Discrete Algorithms. 422\u2013433","author":"Gusfield D.","unstructured":"D. Gusfield and D. Naor . 1990. Efficient Algorithms for Generalized Cut Trees . In Proceedings First ACM-SIAM Symposium on Discrete Algorithms. 422\u2013433 . D. Gusfield and D. Naor. 1990. Efficient Algorithms for Generalized Cut Trees. In Proceedings First ACM-SIAM Symposium on Discrete Algorithms. 422\u2013433."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908632"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283398"},{"key":"e_1_3_2_1_37_1","volume-title":"Flow trees for vertex-capacitated networks. Discrete applied mathematics, 155, 4","author":"Hassin Refael","year":"2007","unstructured":"Refael Hassin and Asaf Levin . 2007. Flow trees for vertex-capacitated networks. Discrete applied mathematics, 155, 4 ( 2007 ), 572\u2013578. Refael Hassin and Asaf Levin. 2007. Flow trees for vertex-capacitated networks. Discrete applied mathematics, 155, 4 (2007), 572\u2013578."},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings 47th Annual ACM Symposium on Theory of Computing (STOC). 21\u201330","author":"Henzinger M.","unstructured":"M. Henzinger , S. Krinninger , D. Nanongkai , and T. Saranurak . 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture . In Proceedings 47th Annual ACM Symposium on Theory of Computing (STOC). 21\u201330 . M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Proceedings 47th Annual ACM Symposium on Theory of Computing (STOC). 21\u201330."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_32"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.001"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00222-5"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS). 793\u2013801","author":"Kanevsky A.","unstructured":"A. Kanevsky , R. Tamassia , G. Di Battista , and J. Chen . 1991. On-Line Maintenance of the Four-Connected Components of a Graph . In Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS). 793\u2013801 . A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. 1991. On-Line Maintenance of the Four-Connected Components of a Graph. In Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS). 793\u2013801."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_44_1","volume-title":"Karger and Debmalya Panigrahi","author":"David","year":"2009","unstructured":"David R. Karger and Debmalya Panigrahi . 2009 . A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 246\u2013255. http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496798 David R. Karger and Debmalya Panigrahi. 2009. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 246\u2013255. http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496798"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721855"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00017"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451112"},{"key":"e_1_3_2_1_52_1","unstructured":"Jason Li Debmalya Panigrahi and Thatchaphol Saranurak. 2021. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Accepted to FOCS\u201921 arXiv:2106.02233  Jason Li Debmalya Panigrahi and Thatchaphol Saranurak. 2021. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Accepted to FOCS\u201921 arXiv:2106.02233"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_2_1_56_1","unstructured":"Zeev Nutov. 2021. Data structure for node connectivity queries. arXiv preprint arXiv:2110.09102.  Zeev Nutov. 2021. Data structure for node connectivity queries. arXiv preprint arXiv:2110.09102."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0014-1"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.105"},{"key":"e_1_3_2_1_59_1","volume-title":"Combinatorial Optimization II (Mathematical Programming Studies","volume":"16","author":"Picard J.-C.","unstructured":"J.-C. Picard and M. Queyranne . 1980. On the structure of all minimum cuts in a network and applications . In Combinatorial Optimization II (Mathematical Programming Studies , Vol. 13). Springer, 8\u2013 16 . J.-C. Picard and M. Queyranne. 1980. On the structure of all minimum cuts in a network and applications. In Combinatorial Optimization II (Mathematical Programming Studies, Vol. 13). Springer, 8\u201316."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.9"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208019"},{"key":"e_1_3_2_1_62_1","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial Optimization - Polyhedra and Efficiency . Springer . Alexander Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer."},{"key":"e_1_3_2_1_63_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, MD Ps , and \u2113 _1-Regression in Nearly Linear Time for Dense Instances . arxiv:2101.05719. 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 \u2113 _1-Regression in Nearly Linear Time for Dense Instances. arxiv:2101.05719."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519945","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519945","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519945"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":64,"alternative-id":["10.1145\/3519935.3519945","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519945","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}