{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:24:56Z","timestamp":1759883096462,"version":"build-2065373602"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"crossref","award":["HFRI-FM17-431"],"award-info":[{"award-number":["HFRI-FM17-431"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Italian Ministry of University and Research","award":["2022TS4Y3N"],"award-info":[{"award-number":["2022TS4Y3N"]}]},{"name":"Dioni: Computing Infrastructure for Big-Data Processing and Analysis","award":["5047222"],"award-info":[{"award-number":["5047222"]}]},{"name":"Operational Programme \u201cCompetitiveness, Entrepreneurship and Innovation\u201d","award":["NSRF 2014\u20132020"],"award-info":[{"award-number":["NSRF 2014\u20132020"]}]},{"name":"Greece and the European Union"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n            The notions of edge-cuts and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge-cuts and the 4-edge-connected components of a graph have been introduced. In this article, we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer-machine model of computation.\n          <\/jats:p>","DOI":"10.1145\/3757919","type":"journal-article","created":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T22:08:57Z","timestamp":1754604537000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing the 4-Edge-Connected Components of a Graph: An Experimental Study"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9706-7409","authenticated-orcid":false,"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Engineering, University of Ioannina, Ioannina, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9492-9894","authenticated-orcid":false,"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"LUISS University, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2457-4937","authenticated-orcid":false,"given":"Evangelos","family":"Kosinas","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Ioannina, Ioannina, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505751"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/070693217"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/2463676.2465323","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD \u201913)","author":"Chang L.","year":"2013","unstructured":"L. Chang, J. X. Yu, L. Qin, X. Lin, C. Liu, and W. Liang. 2013. Efficiently computing \\( k \\) -edge connected components via graph decomposition. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD \u201913). ACM, 205\u2013216."},{"key":"e_1_3_2_5_2","first-page":"290","article-title":"On the structure of a family of minimal weighted cuts in a graph","author":"Dinitz E. A.","year":"1976","unstructured":"E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. 1976. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization, 290\u2013306. (in Russian).","journal-title":"Studies in Discrete Optimization"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/647673.731495"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009195"},{"issue":"3","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0195-6698(87)80032-X","article-title":"\\( k \\) -connectivity in random graphs","volume":"8","author":"Erd\u00f6s P.","year":"1987","unstructured":"P. Erd\u00f6s and J. Kennedy. 1987. \\( k \\) -connectivity in random graphs. European Journal of Combinatorics 8, 3 (1987), 281\u2013286.","journal-title":"European Journal of Combinatorics"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"e_1_3_2_10_2","first-page":"2046","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920)","author":"Forster S.","year":"2020","unstructured":"S. Forster, D. Nanongkai, L. Yang, T. Saranurak, and S. Yingchareonthawornchai. 2020. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920). SIAM, 2046\u20132065."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/122413.122416"},{"key":"e_1_3_2_13_2","first-page":"1","volume-title":"Proceedings of the 19th International Symposium on Experimental Algorithms (SEA \u201921)","volume":"190","author":"Georgiadis L.","year":"2021","unstructured":"L. Georgiadis, K. Giannis, G. F. Italiano, and E. Kosinas. 2021. Computing vertex-edge cut-pairs and 2-edge cuts in practice. In Proceedings of the 19th International Symposium on Experimental Algorithms (SEA \u201921). LIPIcs, Vol. 190, Schloss Dagstuhl Leibniz-Zentrum f\u00fcr Informatik, Article 20, 1\u201319."},{"key":"e_1_3_2_14_2","first-page":"1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921)","volume":"204","author":"Georgiadis L.","unstructured":"L. Georgiadis, G. F. Italiano, and E. Kosinas. Computing the 4-edge-connected components of a graph in linear time. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 47, 1\u201317."},{"key":"e_1_3_2_15_2","first-page":"1","volume-title":"Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC \u201920)","volume":"181","author":"Georgiadis L.","unstructured":"L. Georgiadis and E. Kosinas. Linear-time algorithms for computing twinless strong articulation points and related problems. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC \u201920). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 181, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Article 38, 1\u201316."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90004-O"},{"key":"e_1_3_2_19_2","first-page":"793","volume-title":"Proceedings 32nd Annual Symposium of Foundations of Computer Science (FOCS \u201991)","author":"Kanevsky A.","year":"1991","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 Annual Symposium of Foundations of Computer Science (FOCS \u201991), 793\u2013801."},{"key":"e_1_3_2_20_2","first-page":"246","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909)","author":"Karger D. R.","unstructured":"D. R. Karger and D. A. Panigrahi. Near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909). Society for Industrial and Applied Mathematics, 246\u2013255."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90017-6"},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the 57th ACM Symposium on Theory of Computing (STOC \u201925)","author":"Korhonen T.","year":"2025","unstructured":"T. Korhonen. 2025. Linear-time algorithms for \\( k \\) -edge-connected components, \\( k \\) -lean tree decompositions, and more. In Proceedings of the 57th ACM Symposium on Theory of Computing (STOC \u201925)."},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"1887","DOI":"10.1137\/1.9781611977912.76","volume-title":"Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924)","author":"Kosinas E.","year":"2024","unstructured":"E. Kosinas. 2024. Computing the 5-edge-connected components in linear time. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924). SIAM, 1887\u20132119."},{"key":"e_1_3_2_24_2","unstructured":"J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2014 from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_3_2_26_2","first-page":"1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921)","volume":"204","author":"Nadara W.","year":"2021","unstructured":"W. Nadara, M. Radecki, M. Smulewicz, and M. Soko\u0142owski. 2021. Determining 4-edge-connected components in linear time. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 71, 1\u201315."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167564"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/1434866"},{"issue":"4","key":"e_1_3_2_29_2","first-page":"513","article-title":"Computing  \\( k \\) -edge-connected components of a multigraph","volume":"76","author":"Nagamochi H.","year":"1993","unstructured":"H. Nagamochi and T. Watanabe. 1993. Computing \\( k \\) -edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 76, 4 (1993), 513\u2013517.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792234226"},{"issue":"2","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0012-365X(85)90079-2","article-title":"\\( k \\) -connectivity in random undirected graphs","volume":"54","author":"Reif J. H.","year":"1985","unstructured":"J. H. Reif, and, P. G. 1985. \\( k \\) -connectivity in random undirected graphs. Discrete Mathematics 54, 2 (1985), 181\u2013191.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_32_2","first-page":"1","volume-title":"Proceedings of the 31st Annual European Symposium on Algorithms (ESA \u201923)","volume":"274","author":"Saranurak T.","year":"2023","unstructured":"T. Saranurak and W. Yuan. 2023. Maximal k-edge-connected subgraphs in almost-linear time for small k. In Proceedings of the 31st Annual European Symposium on Algorithms (ESA \u201923). LIPIcs, Vol. 274, Schloss Dagstuhl Leibniz-Zentrum f\u00fcr Informatik, Article 92, 1\u20139."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2016.08.006"},{"issue":"3","key":"e_1_3_2_34_2","first-page":"410","article-title":"A linear-time algorithm for computing all 3-edge-connected components of a multigraph","volume":"75","author":"Taoka S.","year":"1992","unstructured":"S. Taoka, T. Watanabe, and K. Onaga. 1992. A linear-time algorithm for computing all 3-edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 75, 3 (1992), 410\u2013424.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1269-4"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.003"},{"key":"e_1_3_2_40_2","unstructured":"Y. H. Tsin. 2023. A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs. arXiv:2309.13827. Retrieved from https:\/\/arxiv.org\/abs\/2309.13827"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3757919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:04:25Z","timestamp":1759849465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3757919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3757919"],"URL":"https:\/\/doi.org\/10.1145\/3757919","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2023-04-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}