{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:41Z","timestamp":1781078261460,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_48","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"569-580","source":"Crossref","is-referenced-by-count":17,"title":["Solving Planar k -Terminal Cut in $O(n^{c \\sqrt{k}})$ Time"],"prefix":"10.1007","author":[{"given":"Philip N.","family":"Klein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. In: STOC 1998, pp. 48\u201352 (1998)","DOI":"10.1145\/276698.276711"},{"issue":"4","key":"48_CR2","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.orl.2010.03.003","volume":"38","author":"K.K. Cheung","year":"2010","unstructured":"Cheung, K.K., Harvey, K.: Revisiting a simple algorithm for the planar multiterminal cut problem. Operations Research Letters\u00a038(4), 334\u2013336 (2010)","journal-title":"Operations Research Letters"},{"key":"48_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-48777-8_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"W. Cunningham","year":"1999","unstructured":"Cunningham, W., Tang, L.: Optimal 3-Terminal Cuts and Linear Programming. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 114\u2013125. Springer, Heidelberg (1999)"},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiway cuts. In: STOC 1992, pp. 241\u2013251. ACM (1992)","DOI":"10.1145\/129712.129736"},{"issue":"4","key":"48_CR5","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(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"48_CR6","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(3), 203\u2013222 (1998)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"48_CR7","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. System Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. System Sci."},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. In: STOC 1999, pp. 668\u2013678 (1999)","DOI":"10.1145\/301250.301430"},{"key":"48_CR9","series-title":"LNCS","first-page":"677","volume-title":"ICALP 2012, Part I","author":"D. Marx","year":"2012","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In: Czumaj, A., et al. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 677\u2013688. Springer, Heidelberg (2012)"},{"issue":"1","key":"48_CR10","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. J. Algorithms\u00a039(1), 68\u201377 (2001)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:07Z","timestamp":1620130507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}