{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:37Z","timestamp":1759639057533},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_22","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"283-298","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms for Cut Problems on Trees"],"prefix":"10.1007","author":[{"given":"Iyad","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Weitian","family":"Tong","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Boting","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Fenghui","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"issue":"1\u20133","key":"22_CR1","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: STOC, pp. 459\u2013468 (2011)","key":"22_CR2","DOI":"10.1145\/1993636.1993698"},{"unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S., Yeo, A.: A polynomial kernel for multicut in trees. In: STACS, pp. 183\u2013194 (2009)","key":"22_CR3"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1016\/j.jcss.2012.03.001","volume":"78","author":"J Chen","year":"2012","unstructured":"Chen, J., Fan, J., Kanj, I., Liu, Y., Zhang, F.: Multicut in trees viewed through the eyes of vertex cover. J. Comput. Syst. Sci. 78, 1637\u20131650 (2012)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: SODA, pp. 1713\u20131725 (2012)","key":"22_CR5","DOI":"10.1137\/1.9781611973099.136"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"S Chopra","year":"1991","unstructured":"Chopra, S., Rao, M.: On the multiway cut polyhedron. Networks 21, 51\u201389 (1991)","journal-title":"Networks"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"M Costa","year":"2005","unstructured":"Costa, M., Letocart, L., Roupin, F.: Minimal multicut and maximal integer multiflow: a survey. Eur. J. Oper. Res. 162, 55\u201369 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.endm.2004.03.016","volume":"17","author":"M-C Costa","year":"2004","unstructured":"Costa, M.-C., Billionnet, A.: Multiway cut and integer flow problems in trees. Electron. Notes Discrete Math. 17, 105\u2013109 (2004)","journal-title":"Electron. Notes Discrete Math."},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-38756-2_32","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"X Deng","year":"2013","unstructured":"Deng, X., Lin, B., Zhang, C.: Multi-multiway cut problem on graphs of bounded branch width. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 315\u2013324. Springer, Heidelberg (2013)"},{"key":"22_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"22_CR11","volume-title":"Parameterized Complexity Theory","author":"J Fl\u00fcm","year":"2010","unstructured":"Fl\u00fcm, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2010)"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/net.20081","volume":"46","author":"J Guo","year":"2005","unstructured":"Guo, J., Niedermeier, R.: Fixed-parameter tractability and data reduction for multicut in trees. Networks 46, 124\u2013135 (2005)","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"Kanj, I.A., Lin, G., Liu, T., Tong, W., Xia, G., Xu, J., Yang, B., Zhang, F., Zhang, P., Zhu, B.: Algorithms for cut problems on trees. CoRR, abs\/1304.3653 (2013)","key":"22_CR14","DOI":"10.1007\/978-3-319-12691-3_22"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$ . J. Comput. Syst. Sci. 74, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/978-3-642-31594-7_48","volume-title":"Automata, Languages, and Programming","author":"PN Klein","year":"2012","unstructured":"Klein, P.N., Marx, D.: Solving Planar k -Terminal Cut in $$O(n^{c \\sqrt{k}})$$ time. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 569\u2013580. Springer, Heidelberg (2012)"},{"issue":"1\u20133","key":"22_CR17","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/j.tcs.2006.09.018","volume":"369","author":"A Levin","year":"2006","unstructured":"Levin, A., Segev, D.: Partial multicuts in trees. Theor. Comput. Sci. 369(1\u20133), 384\u2013395 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"22_CR18","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10878-012-9565-9","volume":"27","author":"H Liu","year":"2014","unstructured":"Liu, H., Zhang, P.: On the generalized multiway cut in trees problem. J. Comb. Optim. 27(1), 65\u201377 (2014)","journal-title":"J. Comb. Optim."},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351, 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-642-31594-7_57","volume-title":"Automata, Languages, and Programming","author":"D Marx","year":"2012","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 677\u2013688. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC, pp. 469\u2013478 (2011)","key":"22_CR21","DOI":"10.1145\/1993636.1993699"},{"key":"22_CR22","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"22_CR23","volume-title":"Introduction to Graph Theory","author":"DB West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River (1996)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T11:12:34Z","timestamp":1650625954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}