{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:56Z","timestamp":1759639076579},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401633"},{"type":"electronic","value":"9783642401640"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40164-0_11","type":"book-chapter","created":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T01:01:30Z","timestamp":1374454890000},"page":"84-94","source":"Crossref","is-referenced-by-count":0,"title":["An O *(1.84 k ) Parameterized Algorithm for the Multiterminal Cut Problem"],"prefix":"10.1007","author":[{"given":"Yixin","family":"Cao","sequence":"first","affiliation":[]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Jia-Hao","family":"Fan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for planar multiway cut. In: SODA, pp. 639\u2013655 (2012)","DOI":"10.1137\/1.9781611973099.54"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: STOC, pp. 459\u2013468 (2011)","DOI":"10.1145\/1993636.1993698"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J., Schwartz, R.: Simplex partitioning via exponential clocks and the multiway cut problem. In: STOC, pp. 535\u2013544 (2013)","DOI":"10.1145\/2488608.2488675"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition. In: FOCS, pp. 807\u2013816 (2011)","DOI":"10.1109\/FOCS.2011.34"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"11_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J. Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055(5), 21:1\u201321:19 (2008)","journal-title":"J. ACM"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1090\/dimacs\/005\/07","volume":"5","author":"W.H. Cunningham","year":"1991","unstructured":"Cunningham, W.H.: The optimal multiterminal cut problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a05, 105\u2013120 (1991)","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"issue":"1","key":"11_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M. Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. TOCT\u00a05(1), 3:1\u20133:11 (2013)","journal-title":"TOCT"},{"issue":"4","key":"11_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. Comput.\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"11_CR10","series-title":"Texts in Theoretical Computer Science","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Heidelberg (2011)"},{"key":"11_CR11","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"issue":"1","key":"11_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N. Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms\u00a050(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res.\u00a019(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: Minimum k-way cut of bounded size is fixed-parameter tractable. In: FOCS, pp. 160\u2013169 (2011)","DOI":"10.1109\/FOCS.2011.53"},{"key":"11_CR15","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 k-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)"},{"issue":"3","key":"11_CR16","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(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR17","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":"11_CR18","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"11_CR19","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H. Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, Cambridge (2008)"},{"issue":"4","key":"11_CR20","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00224-009-9215-5","volume":"46","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst.\u00a046(4), 723\u2013736 (2010)","journal-title":"Theory Comput. Syst."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40164-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T01:44:12Z","timestamp":1557971052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40164-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401633","9783642401640"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40164-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}