{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:58:32Z","timestamp":1742932712546,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_39","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"472-484","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms for 2-Route Cut Problems"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_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\u00a039, 43\u201352 (2002)","journal-title":"Networks"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2005.03.009","volume":"339","author":"A. Bagchi","year":"2005","unstructured":"Bagchi, A., Chaudhary, A., Kolman, P.: Short length Menger\u2019s theorem and reliable optical networking. Theoretical Computer Science\u00a0339, 315\u2013332 (2005)","journal-title":"Theoretical Computer Science"},{"key":"39_CR3","unstructured":"Bagchi, A., Chaudhary, A., Kolman, P., Sgall, J.: A simple combinatorial proof for the duality of multiroute flows and cuts. TR 2004-662, Charles Univ. (2004)"},{"issue":"4","key":"39_CR4","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R. Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. SIAM J. Comput.\u00a027(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"39_CR5","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/S0895480100368189","volume":"14","author":"G. Brightwell","year":"2001","unstructured":"Brightwell, G., Oriolo, G., Shepherd, F.B.: Some strategies for reserving resilient capacity. SIAM J. on Discrete Math.\u00a014(4), 524\u2013539 (2001)","journal-title":"SIAM J. on Discrete Math."},{"issue":"2","key":"39_CR6","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, F.B.: Reserving Resilient Capacity for a Single Commodity with Upper Bound Constraints. Networks\u00a041(2), 87\u201396 (2003)","journal-title":"Networks"},{"key":"39_CR7","unstructured":"Bruhn, H., Cerny, J., Hall, A., Kolman, P.: Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. In: Proc. of ACM-SIAM SODA (2007)"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences\u00a060, 564\u2013574 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"39_CR9","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/S0097539701395978","volume":"34","author":"G. C\u0103linescu","year":"2004","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. on Computing\u00a034(2), 358\u2013372 (2004)","journal-title":"SIAM J. on Computing"},{"key":"39_CR10","unstructured":"Chekuri, C.: Lecture notes on Multicut rounding via CKR method, \n                        http:\/\/www.cs.uiuc.edu\/homes\/chekuri\/teaching\/fall2006\/lect15.pdf"},{"key":"39_CR11","doi-asserted-by":"publisher","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. on Computing\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J. on Computing"},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/347476.347478","volume":"47","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM\u00a047, 585\u2013616 (2000)","journal-title":"J. ACM"},{"issue":"2","key":"39_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/S0895480195291874","volume":"13","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Disc. Math.\u00a013(2), 255\u2013267 (2000)","journal-title":"SIAM J. Disc. Math."},{"issue":"4","key":"39_CR14","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation for the subset feedback vertex set problem. SIAM J. on Computing\u00a030(4), 1231\u20131252 (2000)","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"39_CR15","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput.\u00a025(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"key":"39_CR16","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1987","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1987)"},{"key":"39_CR17","unstructured":"Gupta, A., Ravi, R.: Lecture notes on LP solutions as Metrics: MultiCut, and Region Growing, \n                        http:\/\/www.cs.cmu.edu\/afs\/cs\/academic\/class\/15854-f05\/www\/scribe\/lec20.pdf"},{"issue":"1","key":"39_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S089548010138917X","volume":"21","author":"O. G\u00fcnl\u00fck","year":"2007","unstructured":"G\u00fcnl\u00fck, O.: A new min-cut max-flow ratio for multicommodity flows. SIAM J. on Discrete Math.\u00a021(1), 1\u201315 (2007); Preliminary version In: Proc.of IPCO (2002)","journal-title":"SIAM J. on Discrete Math."},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 668\u2013678 (1999)","DOI":"10.1145\/301250.301430"},{"issue":"4","key":"39_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/(SICI)1097-0037(199607)27:4<279::AID-NET3>3.0.CO;2-D","volume":"27","author":"W. Kishimoto","year":"1996","unstructured":"Kishimoto, W.: A method for obtaining the maximum multi-route flow in a network. Networks\u00a027(4), 279\u2013291 (1996)","journal-title":"Networks"},{"issue":"6","key":"39_CR21","doi-asserted-by":"publisher","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\u00a046(6), 787\u2013832 (1999); Prelim. version In: Proc. of IEEE FOCS (1988)","journal-title":"J. ACM"},{"key":"39_CR22","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:28:19Z","timestamp":1714620499000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}