{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:16Z","timestamp":1759637716970},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130724"},{"type":"electronic","value":"9783642130731"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-13073-1_16","type":"book-chapter","created":{"date-parts":[[2010,5,10]],"date-time":"2010-05-10T08:09:58Z","timestamp":1273478998000},"page":"167-179","source":"Crossref","is-referenced-by-count":3,"title":["Multicut Algorithms via Tree Decompositions"],"prefix":"10.1007","author":[{"given":"Reinhard","family":"Pichler","sequence":"first","affiliation":[]},{"given":"Stefan","family":"R\u00fcmmele","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"M.C. Costa","year":"2005","unstructured":"Costa, M.C., L\u00e9tocart, L., Roupin, F.: Minimal multicut and maximal integer multiflow: A survey. European Journal of Operational Research\u00a0162, 55\u201369 (2005)","journal-title":"European Journal of Operational Research"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0196-6774(03)00073-7","volume":"48","author":"G. C\u0103linescu","year":"2003","unstructured":"C\u0103linescu, G., Fernandes, C.G., Reed, B.A.: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Alg.\u00a048, 333\u2013359 (2003)","journal-title":"J. Alg."},{"key":"16_CR3","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. Comput.\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"16_CR4","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\u00a018, 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1959","DOI":"10.1016\/j.dam.2008.11.010","volume":"157","author":"C. Bentz","year":"2009","unstructured":"Bentz, C.: A simple algorithm for multicuts in planar graphs with outer terminals. Discrete Applied Mathematics\u00a0157, 1959\u20131964 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR6","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"16_CR7","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S., Yeo, A.: A polynomial kernel for multicut in trees. In: Proc. STACS 2009. LIPIcs, vol.\u00a03, pp. 183\u2013194 (2009)"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/978-3-642-04128-0_58","volume-title":"Algorithms - ESA 2009","author":"D. Marx","year":"2009","unstructured":"Marx, D., Razgon, I.: Constant ratio fixed-parameter approximation of the edge multicut problem. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 647\u2013658. Springer, Heidelberg (2009)"},{"key":"16_CR9","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.\u00a0351, 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Xiao, M.: Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst. (to appear, 2010)","DOI":"10.1007\/s00224-009-9215-5"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J. Guo","year":"2008","unstructured":"Guo, J., H\u00fcffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. European Journal of Operational Research\u00a0186, 542\u2013553 (2008)","journal-title":"European Journal of Operational Research"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"1908","DOI":"10.1016\/j.dam.2007.09.013","volume":"156","author":"C. Bentz","year":"2008","unstructured":"Bentz, C.: On the complexity of the multicut problem in bounded tree-width graphs and digraphs. Discrete Applied Mathematics\u00a0156, 1908\u20131917 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ipl.2007.03.005","volume":"103","author":"G. Gottlob","year":"2007","unstructured":"Gottlob, G., Lee, S.T.: A logical approach to multicut problems. Inf. Process. Lett.\u00a0103, 136\u2013141 (2007)","journal-title":"Inf. Process. Lett."},{"key":"16_CR14","first-page":"193","volume-title":"Handbook of Theor. Comp. Sci.","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theor. Comp. Sci., vol.\u00a0B, pp. 193\u2013242. Elsevier Science Publishers, Amsterdam (1990)"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Pichler, R., R\u00fcmmele, S., Woltran, S.: Multicut algorithms via tree decompositions. Technical Report DBAI-TR-2010-67, Technische Universit\u00e4t Wien (2010)","DOI":"10.1007\/978-3-642-13073-1_16"},{"key":"16_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer, Berlin (1994)"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-006-1226-x","volume":"47","author":"F. Eijkhof van den","year":"2007","unstructured":"van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica\u00a047, 139\u2013158 (2007)","journal-title":"Algorithmica"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J.\u00a051, 255\u2013269 (2008)","journal-title":"Comput. J."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13073-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T02:46:20Z","timestamp":1559097980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13073-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130724","9783642130731"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13073-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}