{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:11:15Z","timestamp":1787321475969,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Given an undirected graph $G=(V,E)$ and a subset of vertices called terminals $T \\subseteq V$, the element-connectivity $\\elconn_G(u,v)$ of two terminals $u,v \\in T$ is the maximum number of $u$-$v$ paths that are pairwise element-disjoint, that is, disjoint in both edges and nonterminals $V \\setminus T$. (Element-connectivity was first (implicitly) defined by Frank, Ibaraki, and Nagamochi in [J. Graph Theory, 17 (1993), pp. 275--281].) (Element-disjoint paths need not be disjoint in terminals.) Hind and Oellermann [\\em Congr. Numer.}, 113 (1996), pp. 179--204] gave a graph reduction step that preserves the global element-connectivity of the terminals. We show that one can also apply such a reduction step while preserving local connectivity, that is, all the pairwise element-connectivities of the terminals. We illustrate the usefulness of this more general reduction step by giving applications to packing element-disjoint Steiner trees and forests: Given a graph $G$ and disjoint terminal sets $T_1, T_2, \\ldots, T_h$, we seek a maximum number of element-disjoint Steiner forests where each forest connects each $T_i$. We prove that if each $T_i$ is $k$-element-connected, then there exist $\\Omega(\\frac{k}{\\log |T| \\log h})$ element-disjoint Steiner forests, where $T = \\bigcup_i T_i$. If $G$ is planar (or has fixed genus), we show that there exist $\\Omega(k)$ Steiner forests. Our proofs are constructive, giving poly-time algorithms to find these forests; these are the first nontrivial algorithms for packing element-disjoint Steiner forests.<\/jats:p>","DOI":"10.1137\/120882147","type":"journal-article","created":{"date-parts":[[2014,4,8]],"date-time":"2014-04-08T14:56:01Z","timestamp":1396968961000},"page":"577-597","source":"Crossref","is-referenced-by-count":6,"title":["A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests"],"prefix":"10.1137","volume":"28","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,4,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9540-3"},{"key":"atypb2","first-page":"21","volume":"45","author":"Borodin O.V.","year":"1987","journal-title":"Metody Diskret. Analiz"},{"key":"atypb3","unstructured":"C. Chekuri and A. Ene,<i>Personal communication<\/i> 2009."},{"key":"atypb4","first-page":"254","author":"Chekuri C.","year":"2009","journal-title":"Languages and Programming"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/040617339"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1188-4"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290684"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy and S. Khanna,<i>Algorithms for single-source vertex connectivity<\/i> in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 105-114.","DOI":"10.1109\/FOCS.2008.63"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a018"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20274"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"E. Demaine, M.T. Hajiaghayi, and P. Klein,<i>Node-weighted Steiner tree and group Steiner tree in planar graphs<\/i> in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), 2009, pp. 328-340.","DOI":"10.1007\/978-3-642-02927-1_28"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.006"},{"key":"atypb13","first-page":"179","author":"Frank A.","year":"1989","journal-title":"Amsterdam"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0405003"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170302"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00463-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614374"},{"key":"atypb18","first-page":"179","volume":"113","author":"Hind H.R.","year":"1996","journal-title":"Congr. Numer."},{"key":"atypb19","first-page":"113","author":"Ivan\u010do J.","year":"1992","journal-title":"Amsterdam"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120314"},{"key":"atypb21","unstructured":"K. Jain, M. Mahdian, and M. Salavatipour,<i>Packing Steiner trees<\/i> in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 266-274."},{"key":"atypb22","unstructured":"K. Jain, I. M\u01cendoiu, V.V. Vazirani, and D.P. Williamson,<i>A primal-dual schema based approximation algorithm for the element connectivity problem<\/i> in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp. 484-489."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.01.006"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00013-8"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_27"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0044-3"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902503"},{"key":"atypb28","first-page":"145","author":"Mader W.","year":"1978","journal-title":"Amsterdam"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.99"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1919"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.06.003"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120882147","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:11:58Z","timestamp":1787317918000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120882147"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120882147"],"URL":"https:\/\/doi.org\/10.1137\/120882147","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}