{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T02:39:09Z","timestamp":1794364749344,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642029264","type":"print"},{"value":"9783642029271","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_22","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"254-265","source":"Crossref","is-referenced-by-count":15,"title":["A Graph Reduction Step Preserving Element-Connectivity and Applications"],"prefix":"10.1007","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":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Aazami, A., Cheriyan, J., Jampani, K.R.: Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees. Algorithmica (manuscript submitted, 2008)","DOI":"10.1007\/978-3-642-03685-9_1"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., Vondrak, J.: Disjoint Bases in a Polymatroid. Random Structures & Algorithms (to appear)","DOI":"10.1002\/rsa.20274"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Chakraborty, T., Chuzhoy, J., Khanna, S.: Network Design for Vertex Connectivity. In: Proc. of ACM STOC, pp. 167\u2013176 (2008)","DOI":"10.1145\/1374376.1374403"},{"key":"22_CR4","unstructured":"Chekuri, C., Korula, N.: Single-Sink Network Design with Vertex-Connectivity Requirements. In: Proc. of FST&TCS (2008)"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1137\/040617339","volume":"23","author":"C. Chekuri","year":"2008","unstructured":"Chekuri, C., Shepherd, B.: Approximate Integer Decompositions for Undirected Network Design Problems. SIAM J. on Disc. Math.\u00a023(1), 163\u2013177 (2008)","journal-title":"SIAM J. on Disc. Math."},{"key":"22_CR6","unstructured":"Cheriyan, J.: Personal Communication (October 2008)"},{"issue":"1","key":"22_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-005-1188-4","volume":"45","author":"J. Cheriyan","year":"2006","unstructured":"Cheriyan, J., Salavatipour, M.: Hardness and Approximation Results for Packing Steiner Trees. Algorithmica\u00a045(1), 21\u201343 (2006)","journal-title":"Algorithmica"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Salavatipour, M.: Packing Element-disjoint Steiner Trees. ACM Trans. on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290684"},{"issue":"3","key":"22_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00493-006-0016-z","volume":"26","author":"J. Cheriyan","year":"2006","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: Network design via iterative rounding of setpair relaxations. Combinatorica\u00a026(3), 255\u2013275 (2006)","journal-title":"Combinatorica"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Khanna, S.: Algorithms for Single-Source Vertex-Connectivity. In: Proc. of IEEE FOCS, pp. 105\u2013114 (October 2008)","DOI":"10.1109\/FOCS.2008.63"},{"key":"22_CR11","unstructured":"Chuzhoy, J., Khanna, S.: An O(k3 logn)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design, arXiv.org preprint. arXiv:0812.4442v1"},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U. Feige","year":"2002","unstructured":"Feige, U., Halld\u00f3rsson, M., Kortsarz, G., Srinivasan, A.: Approximating the Domatic Number. SIAM J. Comput.\u00a032(1), 172\u2013195 (2002)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"22_CR13","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1016\/j.jcss.2005.05.006","volume":"72","author":"L. Fleischer","year":"2006","unstructured":"Fleischer, L., Jain, K., Williamson, D.P.: Iterative Rounding 2-approximation Algorithms for Minimum-cost Vertex Connectivity Problems. J. of Computer and System Sciences\u00a072(5), 838\u2013867 (2006)","journal-title":"J. of Computer and System Sciences"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0167-5060(08)70459-X","volume":"41","author":"A. Frank","year":"1989","unstructured":"Frank, A.: On Connectivity Properties of Eulerian Digraphs. Annals of Discrete Mathematics\u00a041, 179\u2013194 (1989)","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"22_CR15","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0405003","volume":"5","author":"A. Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. on Discrete Math.\u00a05(1), 22\u201353 (1992)","journal-title":"SIAM J. on Discrete Math."},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/S0166-218X(02)00463-8","volume":"131","author":"A. Frank","year":"2003","unstructured":"Frank, A., Kir\u00e1ly, T., Kriesell, M.: On decomposing a hypergraph into k connected sub-hypergraphs. Discr. Applied Math.\u00a0131(2), 373\u2013383 (2003)","journal-title":"Discr. Applied Math."},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02614374","volume":"78","author":"M. Gr\u00f6tschel","year":"1997","unstructured":"Gr\u00f6tschel, M., Martin, A., Weismantel, R.: The Steiner tree packing problem in VLSI-design. Math. Programming\u00a078, 265\u2013281 (1997)","journal-title":"Math. Programming"},{"key":"22_CR18","first-page":"179","volume":"113","author":"H.R. Hind","year":"1996","unstructured":"Hind, H.R., Oellermann, O.: Menger-type results for three or more vertices. Congressus Numerantium\u00a0113, 179\u2013204 (1996)","journal-title":"Congressus Numerantium"},{"issue":"1","key":"22_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica\u00a021(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"22_CR20","unstructured":"Jain, K., Mahdian, M., Salavatipour, M.: Packing Steiner Trees. In: Proc. of ACM-SIAM SODA, pp. 266\u2013274 (2003)"},{"key":"22_CR21","unstructured":"Jain, K., Mandoiu, I.I., Vazirani, V.V., Williamson, D.P.: A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. In: Proc. of ACM-SIAM SODA, pp. 484\u2013489 (1999)"},{"issue":"3","key":"22_CR22","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/jgt.3190120314","volume":"12","author":"B. Jackson","year":"1998","unstructured":"Jackson, B.: Some Remarks on Arc-connectivity, Vertex splitting, and Orientation in Digraphs. Journal of Graph Theory\u00a012(3), 429\u2013436 (1998)","journal-title":"Journal of Graph Theory"},{"issue":"6","key":"22_CR23","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1016\/j.jctb.2008.01.006","volume":"98","author":"T. Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, T., Lau, L.C.: Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. J. of Combin. Theory B\u00a098(6), 1233\u20131252 (2008)","journal-title":"J. of Combin. Theory B"},{"issue":"3","key":"22_CR24","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G. Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput.\u00a033(3), 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"key":"22_CR25","volume-title":"Handbook on Approx. Algorithms and Metaheuristics","author":"G. Kortsarz","year":"2006","unstructured":"Kortsarz, G., Nutov, Z.: Approximating min-cost connectivity problems. In: Handbook on Approx. Algorithms and Metaheuristics, CRC Press, Boca Raton (2006)"},{"key":"22_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0095-8956(02)00013-8","volume":"88","author":"M. Kriesell","year":"2003","unstructured":"Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph. J. of Combin. Theory B\u00a088, 53\u201363 (2003)","journal-title":"J. of Combin. Theory B"},{"issue":"1","key":"22_CR27","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00493-007-0044-3","volume":"27","author":"L.C. Lau","year":"2007","unstructured":"Lau, L.C.: An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica\u00a027(1), 71\u201390 (2007)","journal-title":"Combinatorica"},{"key":"22_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/11496915_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"L.C. Lau","year":"2005","unstructured":"Lau, L.C.: Packing steiner forests. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol.\u00a03509, pp. 362\u2013376. Springer, Heidelberg (2005)"},{"key":"22_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L. Lov\u00e1sz","year":"1976","unstructured":"Lov\u00e1sz, L.: On some connectivity properties of Eulerian graphs. Acta Math. Hung.\u00a028, 129\u2013138 (1976)","journal-title":"Acta Math. Hung."},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0167-5060(08)70504-1","volume":"3","author":"W. Mader","year":"1978","unstructured":"Mader, W.: A reduction method for edge connectivity in graphs. Ann. Discrete Math.\u00a03, 145\u2013164 (1978)","journal-title":"Ann. Discrete Math."},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: An almost O(logk)-approximation for k-connected subgraphs. In: Proc. of ACM-SIAM SODA, pp. 912\u2013921 (2009)","DOI":"10.1137\/1.9781611973068.99"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:53:39Z","timestamp":1558407219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_22","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}