{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:16:55Z","timestamp":1772468215395,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":24,"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\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["759557 and 715672"],"award-info":[{"award-number":["759557 and 715672"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1750140 and CCF 1955703"],"award-info":[{"award-number":["CCF 1750140 and CCF 1955703"]}],"id":[{"id":"10.13039\/100000001","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.3451088","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"317-329","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Vertex connectivity in poly-logarithmic max-flows"],"prefix":"10.1145","author":[{"given":"Jason","family":"Li","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4468-2675","authenticated-orcid":false,"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark \/ KTH, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8386-7168","authenticated-orcid":false,"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7169-0163","authenticated-orcid":false,"given":"Sorrachai","family":"Yingchareonthawornchai","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_3_1","volume-title":"A Probabilistic Algorithm for Vertex Connectivity of Graphs. Inf. Process. Lett., 15, 3","author":"Becker Michael","year":"1982","unstructured":"Michael Becker, W. Degenhardt, J\u00fcrgen Doenhardt, Stefan Hertel, Gerd Kaninke, W. Kerber, Kurt Mehlhorn, Stefan N\u00e4her, Hans Rohnert, and Thomas Winter. 1982. A Probabilistic Algorithm for Vertex Connectivity of Graphs. Inf. Process. Lett., 15, 3, 1982. Pages 135\u2013136."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Keren Censor-Hillel Mohsen Ghaffari and Fabian Kuhn. 2014. Distributed connectivity decomposition. In PODC. ACM. Pages 156\u2013165.","DOI":"10.1145\/2611462.2611491"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Joseph Cheriyan and Ramakrishna Thurimella. 1991. Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract). In STOC. ACM. Pages 391\u2013401.","DOI":"10.1145\/103418.103460"},{"key":"e_1_3_2_1_6_1","volume-title":"A unifying framework for \\ell _0-sampling algorithms. Distributed Parallel Databases, 32, 3","author":"Cormode Graham","year":"2014","unstructured":"Graham Cormode and Donatella Firmani. 2014. A unifying framework for \\ell _0-sampling algorithms. Distributed Parallel Databases, 32, 3, 2014. Pages 315\u2013335."},{"key":"e_1_3_2_1_7_1","volume-title":"Algorithm for solution of a problem of maximal flow in a network with power estimation. 11","author":"Dinic E. A.","year":"1970","unstructured":"E. A. Dinic. 1970. Algorithm for solution of a problem of maximal flow in a network with power estimation. 11, 1970. Pages 1277\u20131280."},{"key":"e_1_3_2_1_8_1","series-title":"SIAM J. Comput., 4, 4","volume-title":"Network Flow and Testing Graph Connectivity","author":"Even Shimon","year":"1975","unstructured":"Shimon Even and Robert Endre Tarjan. 1975. Network Flow and Testing Graph Connectivity. SIAM J. Comput., 4, 4, 1975. Pages 507\u2013518."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Sebastian Forster Danupon Nanongkai Thatchaphol Saranurak Liu Yang and Sorrachai Yingchareonthawornchai. 2020. Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. In SODA. SIAM. Pages 2046\u20132065.","DOI":"10.1137\/1.9781611975994.126"},{"key":"e_1_3_2_1_10_1","series-title":"Lecture Notes in Computer Science. 6198","volume-title":"ICALP (1)","author":"Georgiadis Loukas","unstructured":"Loukas Georgiadis. 2010. Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs. In ICALP (1). Lecture Notes in Computer Science. 6198, Springer. Pages 738\u2013749."},{"key":"e_1_3_2_1_11_1","volume-title":"Goldberg and Robert Endre Tarjan","author":"Andrew","year":"1988","unstructured":"Andrew V. Goldberg and Robert Endre Tarjan. 1988. A new approach to the maximum-flow problem. J. ACM, 35, 4, 1988. Pages 921\u2013940."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.125"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1055"},{"key":"e_1_3_2_1_15_1","volume-title":"Hopcroft and Robert Endre Tarjan","author":"John","year":"1973","unstructured":"John E. Hopcroft and Robert Endre Tarjan. 1973. Dividing a Graph into Triconnected Components. SIAM J. Comput., 2, 3, 1973. Pages 135\u2013158."},{"key":"e_1_3_2_1_16_1","volume-title":"Improved Algorithms for Graph Four-Connectivity. J. Comput. Syst. Sci., 42, 3","author":"Kanevsky Arkady","year":"1991","unstructured":"Arkady Kanevsky and Vijaya Ramachandran. 1991. Improved Algorithms for Graph Four-Connectivity. J. Comput. Syst. Sci., 42, 3, 1991. Pages 288\u2013306."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1969.1082941"},{"key":"e_1_3_2_1_19_1","volume-title":"Deterministic Min-cut in Poly-logarithmic Max-Flows. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Li Jason","year":"2020","unstructured":"Jason Li and Debmalya Panigrahi. 2020. Deterministic Min-cut in Poly-logarithmic Max-Flows. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society."},{"key":"e_1_3_2_1_20_1","volume-title":"Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8, 1","author":"Linial Nathan","year":"1988","unstructured":"Nathan Linial, L\u00e1szl\u00f3 Lov\u00e1sz, and Avi Wigderson. 1988. Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8, 1, 1988. Pages 91\u2013102."},{"key":"e_1_3_2_1_21_1","volume-title":"A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph. Algorithmica, 7, 5&6","author":"Nagamochi Hiroshi","year":"1992","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki. 1992. A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph. Algorithmica, 7, 5&6, 1992. Pages 583\u2013596."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Danupon Nanongkai Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. 2019. Breaking quadratic time for small vertex connectivity and an approximation scheme. In STOC. ACM. Pages 241\u2013252.","DOI":"10.1145\/3313276.3316394"},{"key":"e_1_3_2_1_23_1","volume-title":"An algorithm for finding the edge connectivity of graphs. Vopr. Kibern, 2","author":"Podderyugin VD","year":"1973","unstructured":"VD Podderyugin. 1973. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern, 2, 1973. Pages 136."},{"key":"e_1_3_2_1_24_1","series-title":"SIAM J. Comput., 1, 2","volume-title":"Depth-First Search and Linear Graph Algorithms","author":"Tarjan Robert Endre","year":"1972","unstructured":"Robert Endre Tarjan. 1972. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput., 1, 2, 1972. Pages 146\u2013160."}],"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.3451088","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451088","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451088","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.3451088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":24,"alternative-id":["10.1145\/3406325.3451088","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451088","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"}}]}}