{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:10:02Z","timestamp":1774415402737,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540311980","type":"print"},{"value":"9783540322177","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_28","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T11:37:18Z","timestamp":1136461038000},"page":"303-312","source":"Crossref","is-referenced-by-count":8,"title":["Complexity and Exact Algorithms for Multicut"],"prefix":"10.1007","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[]},{"given":"Falk","family":"H\u00fcffner","sequence":"additional","affiliation":[]},{"given":"Erhan","family":"Kenar","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Uhlmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. Journal of Computer and System Sciences\u00a013, 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"28_CR2","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., L\u00e9tocart, L., Roupin, F.: Minimal Multicut and Maximal Integer Multiflow: a Survey. European Journal of Operational Research\u00a0162(1), 55\u201369 (2005)","journal-title":"European Journal of Operational Research"},{"key":"28_CR3","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.: Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width. Journal of Algorithms\u00a048, 333\u2013359 (2003)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"28_CR4","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 Journal on Computing\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0196-8858(92)90017-Q","volume":"13","author":"P.L. Erd\u0151s","year":"1992","unstructured":"Erd\u0151s, P.L., Sz\u00e9kely, L.A.: Evolutionary Trees: an Integer Multicommodity Max-Flow\u2013Min-Cut Theorem. Advances in Applied Mathematics\u00a013, 375\u2013389 (1992)","journal-title":"Advances in Applied Mathematics"},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica\u00a018(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R.: Exact Algorithms and Applications for Tree-Like Weighted Set Cover. To appear in Journal of Discrete Algorithms (2005)","DOI":"10.1016\/j.jda.2005.07.005"},{"issue":"3","key":"28_CR8","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\u00a046(3), 124\u2013135 (2005)","journal-title":"Networks"},{"key":"28_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-540-28639-4_7","volume-title":"Parameterized and Exact Computation","author":"D. Marx","year":"2004","unstructured":"Marx, D.: Parameterized Graph Separation Problems. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 71\u201382. Springer, Heidelberg (2004); Long version to appear in Theoretical Computer Science"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1287\/opre.10.4.518","volume":"10","author":"A.F. Veinott","year":"1962","unstructured":"Veinott, A.F., Wagner, H.M.: Optimal Capacity Scheduling. Operations Research\u00a010, 518\u2013532 (1962)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:09:29Z","timestamp":1619492969000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/11611257_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}