{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:38Z","timestamp":1750220018350,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T00:00:00Z","timestamp":1670889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council","award":["759557"],"award-info":[{"award-number":["759557"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is\n            <jats:italic>k<\/jats:italic>\n            -connected if it remains connected after removing any\n            <jats:italic>k<\/jats:italic>\n            \u22121  vertices. The vertex connectivity of a graph is the maximum\n            <jats:italic>k<\/jats:italic>\n            such that the graph is\n            <jats:italic>k<\/jats:italic>\n            -connected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near linear-time algorithms for small\n            <jats:italic>k<\/jats:italic>\n            were introduced by Forster et\u00a0al. [SODA 2020]. Prior to that, the best-known algorithm was one by Henzinger et\u00a0al. [FOCS 1996] with quadratic running time when\n            <jats:italic>k<\/jats:italic>\n            is small.\n          <\/jats:p>\n          <jats:p>In this article, we study the practical performance of the algorithms by Forster et\u00a0al. In addition, we introduce a new heuristic on a key subroutine called local cut detection, which we call degree counting. We prove that the new heuristic improves space-efficiency (which can be good for caching purposes) and allows the subroutine to terminate earlier. According to experimental results on random graphs with planted vertex cuts, random hyperbolic graphs, and real-world graphs with vertex connectivity between 4 and 8, the degree counting heuristic offers a factor of 2\u20134 speedup over the original non-degree counting version for small graphs and almost 20 times for some graphs with millions of edges. It also outperforms the previous state-of-the-art algorithm by Henzinger et\u00a0al., even on relatively small graphs.<\/jats:p>","DOI":"10.1145\/3564822","type":"journal-article","created":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T13:22:39Z","timestamp":1666704159000},"page":"1-29","source":"Crossref","is-referenced-by-count":0,"title":["Engineering Nearly Linear-time Algorithms for Small Vertex Connectivity"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3583-8033","authenticated-orcid":false,"given":"Max","family":"Franck","sequence":"first","affiliation":[{"name":"Department of Computer Science, Aalto University, Espoo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7169-0163","authenticated-orcid":false,"given":"Sorrachai","family":"Yingchareonthawornchai","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalto University, Espoo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_3_3_3_2","unstructured":"Josh Alman and Virginia Vassilevska Williams. 2020. A refined laser method and faster matrix multiplication. Retrieved from https:\/\/arxiv.org\/abs\/2010.05846."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.124"},{"key":"e_1_3_3_6_2","first-page":"324","volume-title":"Proceedings of the SODA","author":"Chekuri Chandra","year":"1997","unstructured":"Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Clifford Stein. 1997. Experimental study of minimum cut algorithms. In Proceedings of the SODA. ACM\/SIAM, 324\u2013333."},{"key":"e_1_3_3_7_2","first-page":"49:1\u201349:16","volume-title":"Proceedings of the ICALP (LIPIcs)","volume":"198","author":"Chekuri Chandra","year":"2021","unstructured":"Chandra Chekuri and Kent Quanrud. 2021. Faster algorithms for rooted connectivity in directed graphs. In Proceedings of the ICALP (LIPIcs), Vol. 198. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 49:1\u201349:16."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302965"},{"key":"e_1_3_3_9_2","first-page":"218","volume-title":"Essays in Memory of Shimon Even (Lecture Notes in Computer Science)","author":"Dinitz Yefim","year":"2006","unstructured":"Yefim Dinitz. 2006. Dinitz\u2019 algorithm: The original version and Even\u2019s version. In Essays in Memory of Shimon Even (Lecture Notes in Computer Science), Vol. 3895. Springer, 218\u2013240."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204034"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.126"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1183907.1183912"},{"key":"e_1_3_3_14_2","unstructured":"Yu Gao Jason Li Danupon Nanongkai Richard Peng Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. 2019. Deterministic graph cuts in subquadratic time: Sparse balanced and k-vertex. Retrieved from https:\/\/arxiv.org\/abs\/1910.07950."},{"key":"e_1_3_3_15_2","first-page":"85","article-title":"An experimental study of algorithms for computing the edge connectivity of a directed graph","author":"Georgiadis Loukas","year":"2021","unstructured":"Loukas Georgiadis, Dionysios Kefallinos, Luigi Laura, and Nikos Parotsidis. 2021. An experimental study of algorithms for computing the edge connectivity of a directed graph. In Proceedings of the ALENEX. 85\u201397.","journal-title":"Proceedings of the ALENEX"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240407"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3274662"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548505"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910009"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1969.1082941"},{"key":"e_1_3_3_21_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122557"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(200003)35:2<109::AID-NET2>3.0.CO;2-N"},{"key":"e_1_3_3_25_2","unstructured":"Yang P. Liu and Aaron Sidford. 2020. Faster divergence maximization for faster maximum flow. Retrieved from https:\/\/arxiv.org\/abs\/2003.08929."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316394"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"},{"key":"e_1_3_3_30_2","article-title":"An experimental study of k-vertex connectivity algorithms","author":"Rigat Azzeddine","year":"2012","unstructured":"Azzeddine Rigat. 2012. An experimental study of k-vertex connectivity algorithms. In Proceedings of the INFOCOMP.","journal-title":"Proceedings of the INFOCOMP"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_3_3_32_2","first-page":"919","volume-title":"Proceedings of the FOCS","author":"Brand Jan van den","year":"2020","unstructured":"Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2020. Bipartite matching in nearly linear time on moderately dense graphs. In Proceedings of the FOCS. IEEE, 919\u2013930."},{"key":"e_1_3_3_33_2","first-page":"467","volume-title":"Proceedings of the ISAAC (Lecture Notes in Computer Science)","volume":"9472","author":"Looz Moritz von","year":"2015","unstructured":"Moritz von Looz, Henning Meyerhenke, and Roman Prutkin. 2015. Generating random hyperbolic graphs in subquadratic time. In Proceedings of the ISAAC (Lecture Notes in Computer Science), Vol. 9472. Springer, 467\u2013478."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1111\/0081-1750.00098"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564822","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:23Z","timestamp":1750182683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,13]]},"references-count":33,"alternative-id":["10.1145\/3564822"],"URL":"https:\/\/doi.org\/10.1145\/3564822","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,13]]}}}