{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T21:42:59Z","timestamp":1789940579428,"version":"4.0.1"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We present new edge splitting-off results maintaining all-pairs edge-connectivities of an undirected graph. We first give an alternate proof of Mader's theorem, and use it to obtain a deterministic $\\tilde{O}(m + {r_{\\max}}^2 \\cdot n^2)$-time complete edge splitting-off algorithm for unweighted graphs, where $r_{\\max}$ denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of $\\tilde{\\Omega}(n)$. We then prove a new structural property, and use it to further speed up the algorithm to obtain a randomized $\\tilde{O}(m + {r_{\\max}}^3 \\cdot n)$-time algorithm. These edge splitting-off algorithms can be used directly to speed up various graph algorithms.<\/jats:p>","DOI":"10.1137\/100790239","type":"journal-article","created":{"date-parts":[[2013,6,20]],"date-time":"2013-06-20T09:22:04Z","timestamp":1371720124000},"page":"1185-1200","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities"],"prefix":"10.1137","volume":"42","author":[{"given":"Lap Chi","family":"Lau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chun Kong","family":"Yung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142993226983"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197318878"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1093"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Bhalgat, R. Hariharan, T. Kavitha and D. Panigrahi,\n                      An $\\tilde{O}(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs\n                      , Proceedings of the 39th Annual ACM Symposium on Theory of Computing, (2007), pp. 605-614,","DOI":"10.1145\/1250790.1250879"},{"key":"atypb5","unstructured":"A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi,\n                      Fast edge splitting and Edmonds' arborescence construction for unweighted graphs\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 455-464."},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Y. H. Chan, W. S. Fung, L. C. Lau, and C. K. Yung,\n                      Degree bounded network design with metric costs\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 125-134.","DOI":"10.1109\/FOCS.2008.28"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050041"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"H. Y. Cheung, L. C. Lau, and K. M. Leung,\n                      Graph connectivities, network coding, and expander graphs\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011, pp. 190-199.","DOI":"10.1109\/FOCS.2011.55"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0405003"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90589-8"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200003"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"H. N. Gabow,\n                      Efficient splitting off algorithms for graphs\n                      , in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 696-705.","DOI":"10.1145\/195058.195436"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580607"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"atypb15","unstructured":"R. Hariharan, T. Kavitha, and D. Panigrahi,\n                      Efficient algorithms for computing all low s-t edge connectivities and related problems\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, (2007), pp. 127-136."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00465-1"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0044-3"},{"key":"atypb18","unstructured":"L. Lov\u00e1sz,\n                      Lecture\n                      , Presented at Conference of Graph Theory, Prague, 1974."},{"key":"atypb19","unstructured":"L. Lov\u00e1sz,\n                      Combinatorial Problems and Exercises\n                      , North-Holland, Amsterdam, 1979."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"atypb21","first-page":"1263","author":"Nagamochi H.","year":"2006","journal-title":"Communications and Computer Sciences"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009739202898"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-049-6"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.05.046"},{"key":"atypb26","unstructured":"C. K. Yung,\n                      Edge Splitting-Off and Network Design Problems\n                      , MS thesis, The Chinese University of Hong Kong, 2009."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100790239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:13Z","timestamp":1787337073000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100790239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100790239"],"URL":"https:\/\/doi.org\/10.1137\/100790239","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}