{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:30Z","timestamp":1770993990768,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,29]],"date-time":"2008-01-29T00:00:00Z","timestamp":1201564800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00453-008-9171-5","type":"journal-article","created":{"date-parts":[[2008,1,28]],"date-time":"2008-01-28T15:17:58Z","timestamp":1201533478000},"page":"198-213","source":"Crossref","is-referenced-by-count":5,"title":["Approximation Algorithms for Requirement Cut on\u00a0Graphs"],"prefix":"10.1007","volume":"56","author":[{"given":"Viswanath","family":"Nagarajan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,29]]},"reference":[{"key":"9171_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0894-0347-07-00573-5","volume":"21","author":"S. Arora","year":"2008","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. J.\u00a0Am. Math. Soc. 21, 1\u201321 (2008)","journal-title":"J.\u00a0Am. Math. Soc."},{"key":"9171_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp.\u00a0222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"issue":"1","key":"9171_CR3","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(log\u2009k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J.\u00a0Comput. 27(1), 291\u2013301 (1998)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1\u20133","key":"9171_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2007.02.026","volume":"377","author":"A. Avidor","year":"2007","unstructured":"Avidor, A., Langberg, M.: The multi-multiway cut problem. Theor. Comput. Sci. 377(1\u20133), 35\u201342 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9171_CR5","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. J.\u00a0Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"9171_CR6","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1137\/S0895480104445095","volume":"20","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Guha, S.: The Steiner k-cut problem. SIAM J.\u00a0Discrete Math. 20(1), 261\u2013271 (2006)","journal-title":"SIAM J.\u00a0Discrete Math."},{"issue":"4","key":"9171_CR7","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.\u00a0Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"3","key":"9171_CR8","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A\u00a0tight bound on approximating arbitrary metrics by tree metrics. J.\u00a0Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"4","key":"9171_CR9","first-page":"634","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A\u00a0threshold of ln\u2009n for approximating set cover. J.\u00a0ACM 45(4), 634\u2013652 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"9171_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-(multi)cut theorems and their applications. SIAM J.\u00a0Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"3","key":"9171_CR11","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"D.R. Karger","year":"2004","unstructured":"Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding for minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9171_CR12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1006\/jagm.1996.0833","volume":"22","author":"P.N. Klein","year":"1997","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J.\u00a0Algorithms 22(2), 241\u2013269 (1997)","journal-title":"J.\u00a0Algorithms"},{"issue":"1","key":"9171_CR13","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P.N. Klein","year":"1995","unstructured":"Klein, P.N., Ravi, R.: A\u00a0nearly best-possible approximation algorithm for node-weighted Steiner trees. J.\u00a0Algorithms 19(1), 104\u2013115 (1995)","journal-title":"J.\u00a0Algorithms"},{"key":"9171_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01200755","volume":"15","author":"P.N. Klein","year":"1995","unstructured":"Klein, P.N., Rao, S., Agarwal, A., Ravi, R.: An approximate max-flow min-cut relation for multicommodity flow, with applications. Combinatorica 15, 187\u2013202 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"9171_CR15","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1002\/rsa.10038","volume":"20","author":"G. Konjevod","year":"2002","unstructured":"Konjevod, G., Ravi, R., Srinivasan, A.: Approximation algorithms for the covering Steiner problem. Random Struct. Algorithms 20(3), 465\u2013482 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"9171_CR16","first-page":"787","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.\u00a0ACM 46(6), 787\u2013832 (1999)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"9171_CR17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"2005","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (2005)","journal-title":"Combinatorica"},{"key":"9171_CR18","doi-asserted-by":"crossref","unstructured":"Ford, L.R., Jr., Fulkerson, D.R.: Maximal flow through a network. Can. J.\u00a0Math. 8 (1956)","DOI":"10.4153\/CJM-1956-045-5"},{"key":"9171_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9171_CR20","doi-asserted-by":"crossref","unstructured":"Nagarajan, V., Ravi, R.: Approximation algorithms for requirement cut on graphs. In: Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp.\u00a0209\u2013220 (2005)","DOI":"10.1007\/11538462_18"},{"key":"9171_CR21","unstructured":"Naor, J., Rabani, Y.: Tree packing and approximating k-cuts. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a026\u201327 (2001)"},{"key":"9171_CR22","unstructured":"Ravi, R., Sinha, A.: Approximating k-cuts via network strength. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0621\u2013622 (2002)"},{"issue":"1","key":"9171_CR23","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H. Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k cuts within twice the optimal. SIAM J.\u00a0Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J.\u00a0Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9171-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9171-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9171-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:01Z","timestamp":1559123101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9171-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,29]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9171"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9171-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,29]]}}}