{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T02:07:19Z","timestamp":1780538839580,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540407706","type":"print"},{"value":"9783540451983","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_4","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"36-46","source":"Crossref","is-referenced-by-count":30,"title":["An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor"],"prefix":"10.1007","author":[{"given":"Jittat","family":"Fakcharoenphol","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Adel\u2019son-Vel\u2019ski, G., Dinits, E., Karzanov, A.: Flow Algorithms, Nauka, Moscow (1975) (in Russian)"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput.\u00a027(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Cohen, E., Fiat, A., Kaplan, H., R\u00e4cke, H.: Optimal oblivious routing in polynomial time. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (2003)","DOI":"10.1145\/780542.780599"},{"issue":"2","key":"4_CR4","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences\u00a028(2), 300\u2013343 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Bienkowski, M., Korzeniowski, M., R\u00e4cke, H.: A practical algorithm for constructing oblivious routing schemes. In: Fifteenth ACM Symposium on Parallelism in Algorithms and Architectures (June 2003)","DOI":"10.1145\/777412.777418"},{"key":"4_CR6","first-page":"8","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001)","author":"G. Calinescu","year":"2001","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-Extension problem. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001), January 7\u20139, pp. 8\u201316. ACM Press, New York (2001)"},{"key":"4_CR7","first-page":"379","volume-title":"Proceedings 39th Annual Symposium on Foundations of Computer Science","author":"M. Charikar","year":"1998","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: IEEE (ed.) Proceedings 39th Annual Symposium on Foundations of Computer Science, Palo Alto, California, pp. 379\u2013388. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TIT.1956.1056816","volume":"IT-2","author":"P. Elias","year":"1956","unstructured":"Elias, P., Feinstein, A., Shannon, C.E.: A note on the maximum flow through a network. IEEE Trans. Inform. Th.\u00a0IT-2, 117\u2013119 (1956)","journal-title":"IEEE Trans. Inform. Th."},{"key":"4_CR9","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton Univ. Press, Princeton (1962)"},{"key":"4_CR10","first-page":"47","volume-title":"Paths, Flows and VLSI-Layouts","author":"A. Frank","year":"1990","unstructured":"Frank, A.: Packing paths, circuits, and cuts - a survey. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.-J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layouts, pp. 47\u2013100. Springer, Heidelberg (1990)"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1145\/167088.167266","volume-title":"Proceedings of the twenty-fifth annual ACM symposium on Theory of computing","author":"N. Garg","year":"1993","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 698\u2013707. ACM Press, New York (1993)"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/3-540-47867-1_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"O. G\u00fcnl\u00fck","year":"2002","unstructured":"G\u00fcnl\u00fck, O.: A new min-cut max-flow ratio for multicommodity flows. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 54\u201366. Springer, Heidelberg (2002)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Symposium on Parallel Algorithms and Architectures (2003)","DOI":"10.1145\/777412.777419"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T. Hu","year":"1963","unstructured":"Hu, T.: Multicommodity network flows. Operations Research\u00a011, 344\u2013360 (1963)","journal-title":"Operations Research"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1145\/167088.167261","volume-title":"Proceedings of the twenty-fifth annual ACM symposium on Theory of computing","author":"P. Klein","year":"1993","unstructured":"Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 682\u2013690. ACM Press, New York (1993)"},{"issue":"2","key":"4_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01200755","volume":"15","author":"P.N. Klein","year":"1995","unstructured":"Klein, P.N., Rao, S., Agrawal, A., Ravi, R.: An approximate max-flow min-cut relation for unidirected multicommodity flow, with applications. Combinatorica\u00a015(2), 187\u2013202 (1995)","journal-title":"Combinatorica"},{"key":"4_CR17","first-page":"217","volume":"15","author":"K. Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sue le probl\u00e8me des courbes gauches en topologie. Fund. Math.\u00a015, 217\u2013283 (1930)","journal-title":"Fund. Math."},{"key":"4_CR18","first-page":"422","volume-title":"29th Annual Symposium on Foundations of Computer Science","author":"T. Leighton","year":"1988","unstructured":"Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, October 24\u201326, pp. 422\u2013431. IEEE, Los Alamitos (1988)"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. COMBINAT: Combinatorica\u00a015 (1995)","DOI":"10.1007\/BF01200757"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(85)90004-6","volume":"11","author":"M.V. Lomonosov","year":"1985","unstructured":"Lomonosov, M.V.: Combinatorial approaches to multiflow problems. Discrete Applied Math.\u00a011, 1\u201394 (1985)","journal-title":"Discrete Applied Math."},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1109\/SFCS.1997.646117","volume-title":"38th Annual Symposium on Foundations of Computer Science","author":"B.M. Maggs","year":"1997","unstructured":"Maggs, B.M., auf der Heide, F.M., V\u00f6cking, B., Westermann, M.: Exploiting locality for data management in systems of limited bandwidth. In: 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, October 1997, pp. 284\u2013293. IEEE, Los Alamitos (1997)"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H. Okamura","year":"1981","unstructured":"Okamura, H., Seymour, P.: Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B\u00a031, 75\u201381 (1981)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Tardos, \u00c9.: Improved bounds on the max-flow min-cut ratio for multicommodity flows. In: ACM Symposium on Theory of Computing, pp. 691\u2013697 (1993)","DOI":"10.1145\/167088.167263"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y.: On average distortion of embedding metrics into l1 and into the line yuri rabinovich. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (2003)","DOI":"10.1145\/780606.780609"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Minimizing congestion in general networks. In: Proceedings of the 43rd Annual Symposium on the Foundations of Comuter Science, pp. 43\u201352 (November 2002)","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/304893.304983","volume-title":"Proceedings of the fifteenth annual symposium on Computational geometry","author":"S. Rao","year":"1999","unstructured":"Rao, S.: Small distortion and volume preserving embeddings for planar and euclidean metrics. In: Proceedings of the fifteenth annual symposium on Computational geometry, pp. 300\u2013306. ACM Press, New York (1999)"},{"key":"4_CR27","unstructured":"Rao, S., Richa, A.W.: New approximation techniques for some ordering problems. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, January 25\u201327, pp. 211\u2013218 (1998)"},{"issue":"2","key":"4_CR28","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. a Kuratowski theorem for general surfaces. Journal of Combinatorial Theory Series B\u00a048(2), 255\u2013288 (1990)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1287\/opre.14.3.377","volume":"14","author":"B. Rothschild","year":"1966","unstructured":"Rothschild, B., Whinston, A.: On two commodity network flows. Operations Res.\u00a014, 377\u2013387 (1966)","journal-title":"Operations Res."},{"key":"4_CR30","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0195-6698(81)80033-9","volume":"2","author":"P. Seymour","year":"1981","unstructured":"Seymour, P.: Matroids and multicommodity flows. European Journal of Combinatorics\u00a02, 257\u2013290 (1981)","journal-title":"European Journal of Combinatorics"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.3230100108","volume":"10","author":"P.D. Seymour","year":"1980","unstructured":"Seymour, P.D.: Four-terminus flows. Networks\u00a010, 79\u201386 (1980)","journal-title":"Networks"},{"issue":"2","key":"4_CR32","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F. Shahrokhi","year":"1990","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. Journal of the ACM (JACM)\u00a037(2), 318\u2013334 (1990)","journal-title":"Journal of the ACM (JACM)"},{"key":"4_CR33","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90228-2","volume":"47","author":"\u00c9. Tardos","year":"1993","unstructured":"Tardos, \u00c9., Vazirani, V.: Improved bounds for the max-flow min-multicut ratio for planar and kr,r-free graphs. Information Processing Letters\u00a047, 77\u201380 (1993)","journal-title":"Information Processing Letters"},{"key":"4_CR34","unstructured":"Tragoudas, S.: VLSI partitioning approximation algorithms based on multicommodity flow and other techniques. PhD thesis, University of Texas, Dallas (1991)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:26Z","timestamp":1559916326000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}