{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:50:29Z","timestamp":1770483029644,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642332920","type":"print"},{"value":"9783642332937","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_12","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"109-119","source":"Crossref","is-referenced-by-count":2,"title":["A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs"],"prefix":"10.1007","author":[{"given":"C\u00e9dric","family":"Bentz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Klein, P., Mathieu, C.: A polynomial-time approximation scheme for planar multiway cut. In: 23th SODA (2012)","DOI":"10.1137\/1.9781611973099.54"},{"key":"12_CR2","unstructured":"Bentz, C.: R\u00e9solution exacte et approch\u00e9e de probl\u00e8mes de multiflot entier et de multicoupe: algorithmes et complexit\u00e9. PhD Thesis, CNAM, Paris (2006) (in French)"},{"key":"12_CR3","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":"12_CR4","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":"#cr-split#-12_CR5.1","doi-asserted-by":"crossref","unstructured":"Bentz, C.: New results on planar and directed multicuts. In: EUROCOMB 2009 (2009)","DOI":"10.1016\/j.endm.2009.07.034"},{"key":"#cr-split#-12_CR5.2","doi-asserted-by":"crossref","unstructured":"Electronic Notes in Discrete Mathematics, vol.\u00a034, pp. 207-211 (2009)","DOI":"10.1016\/j.endm.2009.07.034"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0196-6774(03)00073-7","volume":"48","author":"G. C\u01celinescu","year":"2003","unstructured":"C\u01celinescu, 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"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.orl.2010.03.003","volume":"38","author":"K. Cheung","year":"2010","unstructured":"Cheung, K., Harvey, K.: Revisiting a simple algorithm for the planar multiterminal cut problem. Operations Research Letters\u00a038, 334\u2013336 (2010)","journal-title":"Operations Research Letters"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, E., Erickson, J.: Tightening non-simple paths and cycles on surfaces. In: 17th SODA, pp. 192\u2013201 (2006)","DOI":"10.1145\/1109557.1109580"},{"key":"12_CR9","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":"12_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"12_CR11","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":"12_CR12","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":"12_CR13","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0166-218X(98)00036-5","volume":"85","author":"D. Hartvigsen","year":"1998","unstructured":"Hartvigsen, D.: The planar multiterminal cut problem. Discrete Applied Mathematics\u00a085, 203\u2013222 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR14","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":"P.N. Klein","year":"2012","unstructured":"Klein, P.N., Marx, D.: Solving Planar \n                k\n                -Terminal Cut in \n                  \n                    \n                  \n                  $O(n^{c \\sqrt{k}})$\n                 Time. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 569\u2013580. Springer, Heidelberg (2012)"},{"key":"12_CR15","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.\u00a07391, pp. 677\u2013688. Springer, Heidelberg (2012)"},{"key":"12_CR16","series-title":"Algorithms and Combinatorics","first-page":"329","volume-title":"Paths, Flows and VLSI-Layout","author":"A. Schrijver","year":"1990","unstructured":"Schrijver, A.: Homotopic routing methods. In: Korte, B., Lovasz, L., Pr\u00f6mel, H.J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layout. Algorithms and Combinatorics, vol.\u00a09, pp. 329\u2013371. Springer, Berlin (1990)"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BF02574704","volume":"6","author":"A. Schrijver","year":"1991","unstructured":"Schrijver, A.: Disjoint Homotopic Paths and Trees in a Planar Graph. Discrete & Computational Geometry\u00a06, 527\u2013574 (1991)","journal-title":"Discrete & Computational Geometry"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1007\/BFb0036950","volume-title":"Automata, Languages and Programming","author":"M. Yannakakis","year":"1983","unstructured":"Yannakakis, M., Kanellakis, P., Cosmadakis, S., Papadimitriou, C.: Cutting and Partitioning a Graph After a Fixed Pattern. In: D\u00edaz, J. (ed.) ICALP 1983. LNCS, vol.\u00a0154, pp. 712\u2013722. Springer, Heidelberg (1983)"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1006\/jagm.2000.1148","volume":"39","author":"W.-C. Yeh","year":"2001","unstructured":"Yeh, W.-C.: A simple algorithm for the planar multiway cut problem. Journal of Algorithms\u00a039, 68\u201377 (2001)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:06:19Z","timestamp":1558314379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}