{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:50Z","timestamp":1781078270239,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"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_57","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"677-688","source":"Crossref","is-referenced-by-count":26,"title":["A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"8","key":"57_CR1","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences\u00a072(8), 1346\u20131367 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"57_CR2","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."},{"key":"57_CR3","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"3","key":"57_CR4","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":"57_CR5","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":"57_CR6","series-title":"LNCS","first-page":"569","volume-title":"ICALP 2012, Part I","author":"P.N. Klein","year":"2012","unstructured":"Klein, P.N., Marx, D.: Solving planar k-terminal cut in time \n                    \n                      \n                    \n                    ${O}(n^{c\\sqrt{k}})$\n                  . In: Czumaj, A., et al. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 569\u2013580. Springer, Heidelberg (2012)"},{"key":"57_CR7","first-page":"41","volume":"84","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS\u00a084, 41\u201371 (2011)","journal-title":"Bulletin of the EATCS"},{"key":"57_CR8","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: FOCS 2007, pp. 338\u2013348 (2007)","DOI":"10.1109\/FOCS.2007.26"}],"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_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:10Z","timestamp":1620130510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}