{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T13:28:50Z","timestamp":1649165330333},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,3,3]],"date-time":"2013-03-03T00:00:00Z","timestamp":1362268800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00224-013-9454-3","type":"journal-article","created":{"date-parts":[[2013,3,2]],"date-time":"2013-03-02T13:17:50Z","timestamp":1362230270000},"page":"341-363","source":"Crossref","is-referenced-by-count":1,"title":["Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing"],"prefix":"10.1007","volume":"53","author":[{"given":"Petr","family":"Kolman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,3,3]]},"reference":[{"key":"9454_CR1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1002\/net.10008","volume":"39","author":"C.C. Aggarwal","year":"2002","unstructured":"Aggarwal, C.C., Orlin, J.B.: On multiroute maximum flows in networks. Networks 39, 43\u201352 (2002)","journal-title":"Networks"},{"issue":"1","key":"9454_CR2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An O(logk) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"key":"9454_CR3","unstructured":"Bagchi, A., Chaudhary, A., Kolman, P., Sgall, J.: A simple combinatorial proof for the duality of multiroute flows and cuts. Technical Report 2004-662, Charles University, Prague (2004)"},{"issue":"1","key":"9454_CR4","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1868237.1868241","volume":"7","author":"G. Baier","year":"2010","unstructured":"Baier, G., Erlebach, T., Hall, A., K\u00f6hler, E., Kolman, P., Pangr\u00e1c, O., Schilling, H., Skutella, M.: Length-bounded cuts and flows. ACM Trans. Algorithms 7(1), 4\u201327 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9454_CR5","volume-title":"Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"S. Barman","year":"2010","unstructured":"Barman, S., Chawla, S.: Region growing for multi-route cuts. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2010)"},{"issue":"1","key":"9454_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2008.v004a001","volume":"4","author":"H. Bruhn","year":"2008","unstructured":"Bruhn, H., \u010cern\u00fd, J., Hall, A., Kolman, P., Sgall, J.: Single source multiroute flows and cuts on uniform capacity networks. Theory Comput. 4(1), 1\u201320 (2008). Preliminary version in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)","journal-title":"Theory Comput."},{"key":"9454_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/978-3-540-70575-8_39","volume-title":"Proceedings of the 35th International Colloquium on Automata (ICALP)","author":"C. Chekuri","year":"2008","unstructured":"Chekuri, C., Khanna, S.: Algorithms for 2-route cut problems. In: Proceedings of the 35th International Colloquium on Automata (ICALP). Lecture Notes in Computer Science, vol. 5125, pp. 472\u2013484 (2008)"},{"issue":"4","key":"9454_CR8","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994). Preliminary version in Proceedings of the 24th ACM Symposium on Theory of Computing (STOC) (1992)","journal-title":"SIAM J. Comput."},{"key":"9454_CR9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximum flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"issue":"2","key":"9454_CR10","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"key":"9454_CR11","unstructured":"Kahale, N.: On reducing the cut ratio to the multicut problem. DIMACS Technical report 93-78 (1993)"},{"issue":"8","key":"9454_CR12","first-page":"1185","volume":"J-76-A","author":"W. Kishimoto","year":"1993","unstructured":"Kishimoto, W., Takeuchi, M.: On m-route flows in a network. IEICE Trans. J-76-A(8), 1185\u20131200 (1993) (in Japanese)","journal-title":"IEICE Trans."},{"key":"9454_CR13","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics (LIPIcs)","author":"P. Kolman","year":"2011","unstructured":"Kolman, P., Scheideler, C.: Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics (LIPIcs) (2011)"},{"key":"9454_CR14","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1137\/1.9781611973099.64","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"P. Kolman","year":"2012","unstructured":"Kolman, P., Scheideler, C.: Approximate duality of multicommodity multiroute flows and cuts: single source case. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 800\u2013810 (2012)"},{"issue":"6","key":"9454_CR15","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. ACM 46(6), 787\u2013832 (1999). Preliminary version in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1988)","journal-title":"J. ACM"},{"key":"9454_CR16","doi-asserted-by":"crossref","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, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"9454_CR17","first-page":"192","volume-title":"Approximation Algorithms for NP-hard Problems","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B.: Cut problems and their application to divide-and-conquer. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, pp. 192\u2013235. PWS, Boston (1997)"},{"key":"9454_CR18","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9454_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D.P. Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9454-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9454-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9454-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:25Z","timestamp":1558698865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9454-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,3]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9454"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9454-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,3]]}}}