{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:44:01Z","timestamp":1787323441410,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of k edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every $2k$\u2013edge-connected graph has k edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding k edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans and Williamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems.<\/jats:p>","DOI":"10.1137\/040617339","type":"journal-article","created":{"date-parts":[[2008,12,18]],"date-time":"2008-12-18T10:09:18Z","timestamp":1229594958000},"page":"163-177","source":"Crossref","is-referenced-by-count":6,"title":["Approximate Integer Decompositions for Undirected Network Design Problems"],"prefix":"10.1137","volume":"23","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,12,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang,\n                      Bounds on fiber minimization in optical networks with fixed fiber capacity\n                      , in Proceedings of the 24th IEEE INFOCOM Conference, Miami, FL, 2005, pp. 409\u2013419.","DOI":"10.1109\/INFCOM.2005.1497910"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang,\n                      Complexity of wavelength assignment in optical network optimization\n                      , in Proceedings of the 25th IEEE INFOCOM Conference, Barcelona, Spain, 2006.","DOI":"10.1109\/INFOCOM.2006.164"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142993226983"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Baum and L. E. Trotter, Jr.\n                      Integer rounding and polyhedral decomposition for totally unimodular systems\n                      , in Optimization and Operations Research, Lecture Notes in Econ. and Math. Systems 157, R. Henn, B. Korte, and W. Oettli, eds., Springer, Berlin, 1978, pp. 15\u201323.","DOI":"10.1007\/978-3-642-95322-4_2"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0602044"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581256"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1542"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10033"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"C. Chekuri, M. Mydlarz, and F. B. Shepherd,\n                      Multicommodity demand flow in a tree and packing integer programs\n                      , ACM Trans. Algorithms, 3 (2007).","DOI":"10.1145\/1273340.1273343"},{"key":"R11","unstructured":"J. Edmonds,\n                      Edge-disjoint branchings\n                      , in Combinatorial Algorithms, B. Rustin, ed., Academic Press, New York, 1973, pp. 91\u201396."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70734-9"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"T. Erlebach, A. Pagourtzis, K. Potika, and S. Stefanakos,\n                      Resource allocation problems in multifiber WDM tree networks\n                      , in Proceedings of Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 2880, Springer, Berlin, 2003, pp. 218\u2013229.","DOI":"10.1007\/978-3-540-39890-5_19"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"T. Fukunaga and H. Nagamochi,\n                      The set connector problem in graphs\n                      , in Proceedings of the 12th IPCO Conference, Ithaca, NY, Mathematical Programming Society, 2007, pp. 484\u2013498.","DOI":"10.1007\/978-3-540-72792-7_36"},{"key":"R15","first-page":"63","volume":"41","author":"Frank A.","year":"1979","journal-title":"Acta Sci. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-6969","issn-type":"print"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Frank,\n                      Applications of relaxed submodularity\n                      , in Proceedings of the International Congress of Mathematicians, Berlin, 1998, Vol. III: Invited Lectures, Documenta Mathematica, Extra Volume ICM 1998, G. Fischer and U. Rehmann, eds., Documenta Mathematica, Berlin, 1998, pp. 343\u2013354.","DOI":"10.4171\/dms\/1-3\/34"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00463-8"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      A 3-approximation for the minimum tree spanning k vertices\n                      , in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, Burlington, VT, 1996, pp. 302\u2013309.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"N. Garg and R. Khandekar,\n                      Fast approximation algorithms for fractional Steiner forest and related problems\n                      , in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, 2002, pp. 500\u2013509.","DOI":"10.1109\/SFCS.2002.1181974"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R21","unstructured":"M. Goemans and D. Williamson,\n                      The primal-dual method for approximation algorithms and its application to network design problems\n                      , in Approximation Algorithms for NP-Hard Problems, D. Hochbaum, ed., PWS, Boston, 1997."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592085"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193258716"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"R26","unstructured":"K. Jain, M. Mahdian, and M. R. Salvatipour,\n                      Packing Steiner trees\n                      , in Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 2003, pp. 266\u2013274."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. Kriesell,\n                      Local spanning trees in graphs and hypergraph decomposition with respect to edge connectivity\n                      , Proceedings of the 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Electron. Notes Discrete Math. 3, Elevier, Amsterdam, 1999.","DOI":"10.1016\/S1571-0653(05)80036-8"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0044-3"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"L. C. Lau,\n                      Packing Steiner forests\n                      , in Proceedings of the 11th IPCO Conference, Berlin, Mathematical Programming Society, 2005, pp. 362\u2013276.","DOI":"10.1007\/11496915_27"},{"key":"R30","unstructured":"L. Lov\u00e1sz,\n                      Unsolved Problems\n                      , in Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975, Congr. Numer., XV, C. St. J. A. Nash-Williams, Win-Sheehan, eds., Utilitas Mathematica, Winnipeg, Manitoba, 1976, pp. 638\u2013685."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"W. Mader,\n                      A reduction method for edge-connectivity in graphs\n                      , in Advances in Graph Theory, Ann. of Discrete Math. 3, B. Bollobas, ed., North\u2013Holland, Amsterdam, 1978, pp. 145\u2013164.","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00246-8"},{"key":"R34","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , John Wiley and Sons, New York, 1987."},{"key":"R35","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer, Berlin, 2003."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01299747"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040617339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:02:36Z","timestamp":1787320956000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040617339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,17]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/040617339"],"URL":"https:\/\/doi.org\/10.1137\/040617339","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,17]]}}}