{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:03:07Z","timestamp":1780495387774,"version":"3.54.1"},"reference-count":60,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T00:00:00Z","timestamp":1775088000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100024370","name":"Governo Italiano Ministero dell'Istruzione dell'Universita e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100024370","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1016\/j.jcss.2026.103801","type":"journal-article","created":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T16:58:20Z","timestamp":1775753900000},"page":"103801","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["On maximal k-edge-connected subgraphs of undirected graphs"],"prefix":"10.1016","volume":"160","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2457-4937","authenticated-orcid":false,"given":"Evangelos","family":"Kosinas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Debasish","family":"Pattanayak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2026.103801_br0010","author":"Aamand"},{"key":"10.1016\/j.jcss.2026.103801_br0020","series-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"440","article-title":"Fully dynamic all-pairs shortest paths with worst-case update-time revisited","author":"Abraham","year":"2017"},{"key":"10.1016\/j.jcss.2026.103801_br0030","series-title":"Proceedings of the 22nd ACM International Conference on Information & Knowledge Management","first-page":"909","article-title":"Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction","author":"Akiba","year":"2013"},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0040","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1103963.1103966","article-title":"Maintaining information in fully dynamic trees with top trees","volume":"1","author":"Alstrup","year":"2005","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0050","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1137\/070705970","article-title":"Randomized approximation schemes for cuts and flows in capacitated graphs","volume":"44","author":"Bencz\u00far","year":"2015","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2026.103801_br0060","series-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","first-page":"365","article-title":"Decremental strongly-connected components and single-source reachability in near-linear time","author":"Bernstein","year":"2019"},{"issue":"24","key":"10.1016\/j.jcss.2026.103801_br0070","doi-asserted-by":"crossref","first-page":"6285","DOI":"10.1016\/j.disc.2007.11.067","article-title":"Generating 3-vertex connected spanning subgraphs","volume":"308","author":"Boros","year":"2008","journal-title":"Discrete Math."},{"issue":"6","key":"10.1016\/j.jcss.2026.103801_br0080","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.14778\/3514061.3514063","article-title":"A near-optimal approach to edge connectivity-based hierarchical graph decomposition","volume":"15","author":"Chang","year":"2022","journal-title":"Proc. VLDB Endow."},{"key":"10.1016\/j.jcss.2026.103801_br0090","series-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data","first-page":"205","article-title":"Efficiently computing k-edge connected components via graph decomposition","author":"Chang","year":"2013"},{"key":"10.1016\/j.jcss.2026.103801_br0100","series-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"1900","article-title":"Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs","author":"Chechik","year":"2017"},{"key":"10.1016\/j.jcss.2026.103801_br0110","series-title":"Introduction to Algorithms","author":"Cormen","year":"2001"},{"issue":"6","key":"10.1016\/j.jcss.2026.103801_br0120","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","article-title":"A new approach to dynamic all pairs shortest paths","volume":"51","author":"Demetrescu","year":"2004","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.jcss.2026.103801_br0130","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/BF01961541","article-title":"On-line maintenance of triconnected components with SPQR-trees","volume":"15","author":"Di Battista","year":"1996","journal-title":"Algorithmica"},{"key":"10.1016\/j.jcss.2026.103801_br0140","series-title":"Graph Theory","author":"Diestel","year":"2000"},{"key":"10.1016\/j.jcss.2026.103801_br0150","series-title":"Studies in Discrete Optimization","first-page":"290","article-title":"On the structure of the system of minimum edge-cuts in a graph","author":"Dinic","year":"1976"},{"key":"10.1016\/j.jcss.2026.103801_br0160","series-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory","first-page":"272","article-title":"Incremental maintenance of the 5-edge-connectivity classes of a graph","author":"Dinitz","year":"2000"},{"key":"10.1016\/j.jcss.2026.103801_br0170","series-title":"Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing","first-page":"509","article-title":"A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance","author":"Dinitz","year":"1995"},{"key":"10.1016\/j.jcss.2026.103801_br0180","series-title":"Graph-Theoretic Concepts in Computer Science, 18th International Workshop, Proceedings","first-page":"145","article-title":"The 3-edge-components and a structural description of all 3-edge-cuts in a graph","volume":"vol. 657","author":"Dinitz","year":"1992"},{"issue":"3","key":"10.1016\/j.jcss.2026.103801_br0190","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/PL00009195","article-title":"Maintaining the classes of 4-edge-connectivity in a graph on-line","volume":"20","author":"Dinitz","year":"1998","journal-title":"Algorithmica"},{"issue":"5","key":"10.1016\/j.jcss.2026.103801_br0200","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/265910.265914","article-title":"Sparsification - a technique for speeding up dynamic graph algorithms","volume":"44","author":"Eppstein","year":"1997","journal-title":"J. ACM"},{"key":"10.1016\/j.jcss.2026.103801_br0210","series-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings","first-page":"2046","article-title":"Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms","author":"Forster","year":"2019"},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0220","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0020-0190(96)00202-5","article-title":"The incremental maintenance of a depth-first-search tree in directed acyclic graphs","volume":"61","author":"Franciosa","year":"1997","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10.1016\/j.jcss.2026.103801_br0230","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","article-title":"Data structures for on-line updating of minimum spanning trees, with applications","volume":"14","author":"Frederickson","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2026.103801_br0240","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1006\/jcss.1995.1022","article-title":"A matroid approach to finding edge connectivity and packing arborescences","volume":"50","author":"Gabow","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2026.103801_br0250","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0020-0190(00)00051-X","article-title":"Path-based depth-first search for strong and biconnected components","volume":"74","author":"Gabow","year":"2000","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.jcss.2026.103801_br0260","series-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing","first-page":"317","article-title":"Fully dynamic algorithms for edge connectivity problems","author":"Galil","year":"1991"},{"issue":"1","key":"10.1016\/j.jcss.2026.103801_br0270","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/122413.122416","article-title":"Reducing edge connectivity to vertex connectivity","volume":"22","author":"Galil","year":"1991","journal-title":"SIGACT News"},{"issue":"1","key":"10.1016\/j.jcss.2026.103801_br0280","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1137\/0222002","article-title":"Maintaining the 3-edge-connected components of a graph on-line","volume":"22","author":"Galil","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2026.103801_br0290","series-title":"44th International Colloquium on Automata, Languages, and Programming","article-title":"Decremental data structures for connectivity and dominators in directed graphs","author":"Georgiadis","year":"2017"},{"key":"10.1016\/j.jcss.2026.103801_br0300","series-title":"29th Annual European Symposium on Algorithms","article-title":"Computing the 4-edge-connected components of a graph in linear time","volume":"vol. 204","author":"Georgiadis","year":"2021"},{"key":"10.1016\/j.jcss.2026.103801_br0310","series-title":"Automata, Languages, and Programming - 42nd International Colloquium, Proceedings, Part I","first-page":"713","article-title":"Finding 2-edge and 2-vertex strongly connected components in quadratic time","volume":"vol. 9134","author":"Henzinger","year":"2015"},{"key":"10.1016\/j.jcss.2026.103801_br0320","series-title":"36th Annual Symposium on Foundations of Computer Science","first-page":"664","article-title":"Fully dynamic biconnectivity and transitive closure","author":"Henzinger","year":"1995"},{"issue":"4","key":"10.1016\/j.jcss.2026.103801_br0330","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/320211.320215","article-title":"Randomized fully dynamic graph algorithms with polylogarithmic time per operation","volume":"46","author":"Henzinger","year":"1999","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.jcss.2026.103801_br0340","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","article-title":"Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity","volume":"48","author":"Holm","year":"2001","journal-title":"J. ACM"},{"key":"10.1016\/j.jcss.2026.103801_br0350","series-title":"25th Annual European Symposium on Algorithms","article-title":"Contracting a planar graph efficiently","volume":"vol. 87","author":"Holm","year":"2017"},{"issue":"3","key":"10.1016\/j.jcss.2026.103801_br0360","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","article-title":"Dividing a graph into triconnected components","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2026.103801_br0370","series-title":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)","first-page":"861","article-title":"Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract)","author":"Jin","year":"2022"},{"key":"10.1016\/j.jcss.2026.103801_br0380","series-title":"Proceedings 32nd Annual Symposium of Foundations of Computer Science (FOCS 1991)","first-page":"793","article-title":"On-line maintenance of the four-connected components of a graph","author":"Kanevsky","year":"1991"},{"key":"10.1016\/j.jcss.2026.103801_br0390","series-title":"Dynamic Graph Algorithms and Data Structures","author":"La Poutr\u00e9","year":"1991"},{"issue":"5","key":"10.1016\/j.jcss.2026.103801_br0400","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1137\/S0097539793257770","article-title":"Maintenance of 2- and 3-edge-connected components of graphs II","volume":"29","author":"La Poutr\u00e9","year":"2000","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"10.1016\/j.jcss.2026.103801_br0410","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0012-365X(93)90376-5","article-title":"Maintenance of 2- and 3-edge- connected components of graphs I","volume":"114","author":"La Poutr\u00e9","year":"1993","journal-title":"Discrete Math."},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0420","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1007\/s11280-019-00725-6","article-title":"Towards k-vertex connected component discovery from large networks","volume":"23","author":"Li","year":"2020","journal-title":"World Wide Web"},{"key":"10.1016\/j.jcss.2026.103801_br0430","series-title":"Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments","first-page":"173","article-title":"2-Connectivity in directed graphs: an experimental study","author":"Di Luigi","year":"2015"},{"key":"10.1016\/j.jcss.2026.103801_br0440","series-title":"29th Annual European Symposium on Algorithms","article-title":"Determining 4-edge-connected components in linear time","volume":"vol. 204","author":"Nadara","year":"2021"},{"issue":"163","key":"10.1016\/j.jcss.2026.103801_br0450","article-title":"A linear time algorithm for computing 3-edge-connected components in a multigraph","volume":"9","author":"Nagamochi","year":"1992","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"10.1016\/j.jcss.2026.103801_br0460","series-title":"Algorithmic Aspects of Graph Connectivity","author":"Nagamochi","year":"2008"},{"issue":"5&6","key":"10.1016\/j.jcss.2026.103801_br0470","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01758778","article-title":"A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph","volume":"7","author":"Nagamochi","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/j.jcss.2026.103801_br0480","series-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"183","article-title":"Maximal k-edge-connected subgraphs in weighted graphs via local random contraction","author":"Nalam","year":"2023"},{"key":"10.1016\/j.jcss.2026.103801_br0490","series-title":"58th IEEE Annual Symposium on Foundations of Computer Science","first-page":"950","article-title":"Dynamic minimum spanning forest with subpolynomial worst-case update time","author":"Nanongkai","year":"2017"},{"key":"10.1016\/j.jcss.2026.103801_br0500","series-title":"Proceedings of the 19th International Colloquium on Automata, Languages and Programming","first-page":"354","article-title":"Maintenance of triconnected components of graphs (extended abstract)","author":"La Poutr\u00e9","year":"1992"},{"key":"10.1016\/j.jcss.2026.103801_br0510","series-title":"Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023)","article-title":"Maximal k-edge-connected subgraphs in almost-linear time for small k","author":"Saranurak","year":"2023"},{"key":"10.1016\/j.jcss.2026.103801_br0520","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.knosys.2016.08.006","article-title":"Efficient k-edge connected component detection through an early merging and splitting strategy","volume":"111","author":"Sun","year":"2016","journal-title":"Knowl.-Based Syst."},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0530","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.jcss.2026.103801_br0540","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/j.jcss.2026.103801_br0550","series-title":"Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings","first-page":"384","article-title":"Fully-dynamic all-pairs shortest paths: faster and allowing negative cycles","author":"Thorup","year":"2004"},{"issue":"1","key":"10.1016\/j.jcss.2026.103801_br0560","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00493-007-0045-2","article-title":"Fully-dynamic min-cut","volume":"27","author":"Thorup","year":"2007","journal-title":"Combinatorica"},{"issue":"1","key":"10.1016\/j.jcss.2026.103801_br0570","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.jda.2008.04.003","article-title":"Yet another optimal algorithm for 3-edge-connectivity","volume":"7","author":"Tsin","year":"2009","journal-title":"J. Discrete Algorithms"},{"key":"10.1016\/j.jcss.2026.103801_br0580","series-title":"35th IEEE International Conference on Data Engineering","first-page":"52","article-title":"Enumerating k-vertex connected components in large graphs","author":"Wen","year":"2019"},{"issue":"5&6","key":"10.1016\/j.jcss.2026.103801_br0590","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF01758773","article-title":"Maintaining bridge-connected and biconnected components on-line","volume":"7","author":"Westbrook","year":"1992","journal-title":"Algorithmica"},{"issue":"7","key":"10.1016\/j.jcss.2026.103801_br0600","doi-asserted-by":"crossref","first-page":"516","DOI":"10.14778\/2904483.2904484","article-title":"I\/O efficient ECC graph decomposition via graph reduction","volume":"9","author":"Yuan","year":"2016","journal-title":"Proc. VLDB Endow."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000026000474?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000026000474?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T13:02:09Z","timestamp":1780491729000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000026000474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":60,"alternative-id":["S0022000026000474"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2026.103801","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2026,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On maximal k-edge-connected subgraphs of undirected graphs","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2026.103801","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier Inc.","name":"copyright","label":"Copyright"}],"article-number":"103801"}}