{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:17:39Z","timestamp":1725520659084},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540767954"},{"type":"electronic","value":"9783540767961"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-76796-1_20","type":"book-chapter","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T07:24:04Z","timestamp":1225956244000},"page":"429-450","source":"Crossref","is-referenced-by-count":2,"title":["Single-Sink Multicommodity Flow with\u00a0Side\u00a0Constraints"],"prefix":"10.1007","author":[{"given":"F. Bruce","family":"Shepherd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/net.10008","volume":"39","author":"C. Aggarwal","year":"2002","unstructured":"Aggarwal, C., Orlin, J.: On multi-route maximum flows in networks. Networks 39, 43\u201352 (2002)","journal-title":"Networks"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"1204","DOI":"10.1109\/18.850663","volume":"46","author":"R. Ahlswede","year":"2000","unstructured":"Ahlswede, R., Cai, N., Li, S.-Y.R., Yeung, R.W.: Network information flow. IEEE Trans. Inf. Theory 46, 1204\u20131216 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"20_CR3","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Zhang, L.: Path decomposition under a new cost measure with applications to optical network design. In: European Symposium on Algorithms (ESA), pp.\u00a028\u201339 (2004)","DOI":"10.1007\/978-3-540-30140-0_5"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1287\/opre.28.5.1074","volume":"28","author":"J.J. Bartholdi","year":"1980","unstructured":"Bartholdi, J.J., Orlin, J.B., Ratliff, H.D.: Cyclic scheduling via integer programs with circular ones. Oper. Res. 28, 1074\u20131085 (1980)","journal-title":"Oper. Res."},{"key":"20_CR6","series-title":"Lecture Notes in Economics and Mathematical Systems","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-642-95322-4_2","volume-title":"Optimization and Operations Research (Proceedings of Workshop Bad Honnef, 1977)","author":"S. Baum","year":"1978","unstructured":"Baum, S., Trotter, L.E. Jr.: Integer rounding and polyhedral decomposition for totally unimodular systems. In: Henn, R., Korte, B., Oettli, W. (eds.) Optimization and Operations Research (Proceedings of Workshop Bad Honnef, 1977). Lecture Notes in Economics and Mathematical Systems, vol.\u00a0157, pp. 15\u201323. Springer, Berlin (1978)"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(97)00137-6","volume":"84","author":"B. Beauquier","year":"1998","unstructured":"Beauquier, B., Hell, P., Perennes, S.: Optimal wavelength-routed multicasting. Discrete Appl. Math. 84, 15\u201320 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"20_CR8","first-page":"165","volume":"233","author":"B. Beauquier","year":"2000","unstructured":"Beauquier, B., Bermond, J.C., Gargano, L., Hell, P., Perennes, S., Vaccaro, U.: Graph problems arising from wavelength-routing in all-optical networks. Theor. Comput. Sci. 233(1\u20132), 165\u2013189 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/PL00011390","volume":"89","author":"D. Bienstock","year":"2000","unstructured":"Bienstock, D., Muratore, G.: Strong inequalities for capacitated survivable network design problems. Math. Program., Ser. A 89, 127\u2013147 (2000)","journal-title":"Math. Program., Ser. A"},{"key":"20_CR10","unstructured":"Brightwell, G., Shepherd, F.B.: Consultancy report: Resilience strategy for a single source-destination pair. LSE CDAM Report 96-22 (August 1996)"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/S0895480100368189","volume":"14","author":"G. Brightwell","year":"2001","unstructured":"Brightwell, G., Oriolo, G., Shepherd, B.: Reserving resilient capacity in a network. SIAM J. Discrete Math. 14, 524\u2013539 (2001)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/net.10064","volume":"41","author":"G. Brightwell","year":"2003","unstructured":"Brightwell, G., Oriolo, G., Shepherd, B.: Reserving resilient capacity for a single commodity with upper bound constraints. Networks 41(2), 87\u201396 (2003)","journal-title":"Networks"},{"key":"20_CR13","unstructured":"Chekuri, C., Khanna, S.: Edge disjoint paths revisited. In: Proc. of the ACM\u2013SIAM Symposium on Discrete Algorithms (SODA) (2003)"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: Proc. of the ACM Symposium on Theory of Computing (STOC) (2004a)","DOI":"10.1145\/1007352.1007383"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: Proc. of IEEE Foundations of Computer Science (FOCS) (2004b)","DOI":"10.1109\/FOCS.2004.27"},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1002\/bltj.20165","volume":"11","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Claisse, P., Essiambre, R., Fortune, S., Kilper, D., Nithi, K., Lee, W., Saniee, I., Shepherd, B., Wilfong, G., White, C., Zhang, L.: Design tools for transparent optical networks. Bell Labs Techn. J. 11(2), 129\u2013143 (2006a)","journal-title":"Bell Labs Techn. J."},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2\u20137","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: An \n\n                \n                  \n                \n                $O(\\sqrt{n})$\n               \napproximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2\u20137, 137\u2013146 (2006b)","journal-title":"Theory Comput."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Chen, J., Rajaraman, R., Sundaram, R.: Meet and merge: approximation algorithms for confluent flow. In: Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pp. 373\u2013382 (2003)","DOI":"10.1145\/780542.780598"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Chen, J., Kleinberg, R., Lovasz, L., Rajaraman, R., Sundaram, R., Vetta, A.: (Almost) tight bounds and existence theorems for confluent flows. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 529\u2013538 (2004)","DOI":"10.1145\/1007352.1007432"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02110141","volume":"3","author":"S. Cosares","year":"1994","unstructured":"Cosares, S., Saniee, I.: An optimization problem related to balancing loads on SONET rings. Telecommun. Syst. 3, 165\u2013181 (1994)","journal-title":"Telecommun. Syst."},{"key":"20_CR21","unstructured":"Costain, G., Kennedy, S., Meagher, C. (eds.): Bellairs Combinatorial Optimization Open Problems. \n                http:\/\/www.math.mcgill.ca\/~bshepherd\/Bellairs\/bellairs2007.pdf"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.: On the single-source unsplittable flow problem. Combinatorica 19, 17\u201341 (1999)","journal-title":"Combinatorica"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Donovan, P., Shepherd, F.B., Vetta, A., Wilfong, G.T.: Degree-constrained network flows. In: Proc. of the ACM Symposium on Theory of Computing (STOC) (2007)","DOI":"10.1145\/1250790.1250889"},{"key":"20_CR24","first-page":"91","volume-title":"Combinatorial Algorithms, Courant Computer Science Symposium 9","author":"J. Edmonds","year":"1973","unstructured":"Edmonds, J.: Edge-disjoint branchings. In: Rustin, R. (ed.) Combinatorial Algorithms, Courant Computer Science Symposium 9, Monterey, CA, 1972, pp. 91\u201396. Academic Press, New York (1973)"},{"issue":"1\u20132","key":"20_CR25","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-005-1161-2","volume":"43","author":"J. Fong","year":"2005","unstructured":"Fong, J., Gilbert, A.C., Kannan, S., Strauss, M.: Better alternatives to OSPF routing. Algorithmica 43(1\u20132), 113\u2013131 (2005)","journal-title":"Algorithmica"},{"key":"20_CR26","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford Jr.","year":"1956","unstructured":"Ford, L.R. Jr., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"20_CR27","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"Ford, L.R. Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Fortune, S., Sweldens, W., Zhang, L.: Line system design for DWDM networks. In: Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks), pp. 315\u2013320 (2004)","DOI":"10.1109\/NETWKS.2004.241053"},{"issue":"4","key":"20_CR29","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1109\/JSAC.2002.1003042","volume":"20","author":"B. Fortz","year":"2002","unstructured":"Fortz, B., Thorup, M.: Optimizing OSPF\/IS-IS weights in a changing world. IEEE J. Sel. Areas Commun. 20(4), 756\u2013767 (2002)","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"1","key":"20_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/1300000003","volume":"2","author":"C. Fragouli","year":"2007","unstructured":"Fragouli, C., Soljanin, E.: Network coding fundamentals. Found. Trends Netw. 2(1), 1\u2013133 (2007)","journal-title":"Found. Trends Netw."},{"key":"20_CR31","unstructured":"Frank, A.: Personal communication (2005)"},{"key":"20_CR32","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/psapm\/010\/0114759","volume-title":"Combinatorial Analysis","author":"A.J. Hoffman","year":"1960","unstructured":"Hoffman, A.J.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Bellman, R., Hall, M. (eds.) Combinatorial Analysis, pp. 113\u2013128. Am. Math. Soc., Providence (1960)"},{"key":"20_CR33","series-title":"Series on Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1142\/3640","volume-title":"The Mathematical Theory of Nonblocking Switching Networks","author":"F.K. Hwang","year":"1998","unstructured":"Hwang, F.K.: The Mathematical Theory of Nonblocking Switching Networks. Series on Applied Mathematics, vol.\u00a011. World Scientific, River Edge (1998)"},{"key":"20_CR34","first-page":"27","volume":"3","author":"M. Iri","year":"1960","unstructured":"Iri, M.: A new method of solving transportation-network problems. J. Oper. Res. Soc. Jpn. 3, 27\u201387 (1960)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01350174","volume":"187","author":"H.A. Jung","year":"1970","unstructured":"Jung, H.A.: Einer Verallgemeinerung des n-fachen Zusammenhangs f\u00fcr Graphen. Math. Ann. 187, 95\u2013103 (1970)","journal-title":"Math. Ann."},{"key":"20_CR36","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Single-source unsplittable flow. In: Proceedings of the 37th Symposium on Foundations of Computer Science (FOCS), pp. 68\u201377 (1996)","DOI":"10.1109\/SFCS.1996.548465"},{"key":"20_CR37","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: Decision algorithms for unsplittable flow and the half-disjoint paths problem. In: Proc. of the ACM Symposium on Theory of Computing (STOC), pp. 530\u2013539 (1998)","DOI":"10.1145\/276698.276867"},{"key":"20_CR38","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In: Proc. of the Foundations of Computer Science (FOCS) (2005)","DOI":"10.1109\/SFCS.2005.18"},{"key":"20_CR39","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S., Stein, C.: Improved approximation algorithms for unsplittable flow problems. In: Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS), pp. 426\u2013435 (1997)","DOI":"10.1109\/SFCS.1997.646131"},{"key":"20_CR40","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Kauffman, Los Altos (1992)"},{"issue":"6","key":"20_CR41","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. Assoc. Comput. Mach. 46(6), 787\u2013832 (1999); Preliminary version in Proc. of the Foundations of Computer Science (FOCS) (1988)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"20_CR42","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995); Preliminary version in Proc. of IEEE Foundations of Computer Science (FOCS) (1994)","journal-title":"Combinatorica"},{"key":"20_CR43","unstructured":"McGregor, A., Shepherd, F.B.: Island hopping and path colouring, with applications to WDM network design. In: Proceedings of the 18th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"20_CR44","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K. Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fund. Math. 10, 96\u2013115 (1927)","journal-title":"Fund. Math."},{"key":"20_CR45","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1090\/psapm\/026\/9888","volume":"26","author":"N. Pippenger","year":"1978","unstructured":"Pippenger, N.: Telephone switching networks. AMS Proc. Symp. Appl. Math. 26, 101\u2013133 (1978)","journal-title":"AMS Proc. Symp. Appl. Math."},{"key":"20_CR46","volume-title":"Communication Networks, Handbook of Theoretical Computer Science (vol.\u00a0A): Algorithms and Complexity","author":"N. Pippenger","year":"1991","unstructured":"Pippenger, N.: Communication Networks, Handbook of Theoretical Computer Science (vol.\u00a0A): Algorithms and Complexity. MIT Press, Cambridge (1991)"},{"key":"20_CR47","unstructured":"R\u00e4cke, H.: Minimizing congestion in general networks. In: Proc. of the Foundations of Computer Science (FOCS) (2002)"},{"key":"20_CR48","volume-title":"Paths, Flows and VLSI-Layout","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Outline of a disjoint paths algorithm. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layout. Springer, New York (1990)"},{"issue":"1","key":"20_CR49","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII: the disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"20_CR50","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"issue":"1","key":"20_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480195294994","volume":"11","author":"A. Schrijver","year":"1998","unstructured":"Schrijver, A., Seymour, P., Winkler, P.: The ring loading problem. SIAM J. Discrete Math. 11(1), 1\u201314 (1998); Reprinted in SIAM Rev. 41(1) 777\u2013791 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR52","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/0-387-25592-3_8","volume-title":"Graph Theory and Combinatorial Optimization","author":"F.B. Shepherd","year":"2005","unstructured":"Shepherd, F.B., Vetta, A.: Visualizing, finding and packing dijoins. In: Avis, D., Hertz, A., Marcotte, O. (eds.) Graph Theory and Combinatorial Optimization, pp. 219\u2013254. Kluwer, New York (2005)"},{"key":"20_CR53","unstructured":"Shepherd, F.B., Wilfong, G.T.: Multilateral transport games. In: INOC (2005)"},{"key":"20_CR54","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M. Skutella","year":"2002","unstructured":"Skutella, M.: Approximating the single source unsplittable min-cost flow problem. Math. Program., Ser. B 91, 493\u2013514 (2002)","journal-title":"Math. Program., Ser. B"},{"key":"20_CR55","unstructured":"Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: Proc. of the ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 830\u2013831 (2003)"},{"key":"20_CR56","doi-asserted-by":"crossref","DOI":"10.1561\/0100000007","volume-title":"Network Coding Theory","author":"R.R. Yeung","year":"2006","unstructured":"Yeung, R.R., Li, S.-Y.R., Cai, N., Zhang, Z.: Network Coding Theory. Now Publishers, Boston (2006)"}],"container-title":["Research Trends in Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-76796-1_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:39:00Z","timestamp":1619519940000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-76796-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540767954","9783540767961"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-76796-1_20","relation":{},"subject":[]}}