{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T07:31:50Z","timestamp":1770276710594,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993698","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"459-468","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Multicut is FPT"],"prefix":"10.1145","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[{"name":"LIRMM, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Daligault","sequence":"additional","affiliation":[{"name":"LIRMM, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"LIRMM, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","series-title":"Dagstuhl Seminar Proceedings","first-page":"183","volume-title":"STACS","author":"Bousquet N.","year":"2009","unstructured":"N. Bousquet , J. Daligault , S. Thomass\u00e9 , and A. Yeo . A polynomial kernel for multicut in trees . In STACS , volume 09001 of Dagstuhl Seminar Proceedings , pages 183 -- 194 , 2009 . N. Bousquet, J. Daligault, S. Thomass\u00e9, and A. Yeo. A polynomial kernel for multicut in trees. In STACS, volume 09001 of Dagstuhl Seminar Proceedings, pages 183--194, 2009."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374404"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.10.037"},{"key":"e_1_3_2_2_6_1","unstructured":"J. Daligault C. Paul A. Perez and S. Thomass\u00e9. Reducing multicut to bounded tree-width. http:\/\/www.lirmm.fr\/~daligault\/MulticutTreewidthReduction.pdf 2010. J. Daligault C. Paul A. Perez and S. Thomass\u00e9. Reducing multicut to bounded tree-width. http:\/\/www.lirmm.fr\/~daligault\/MulticutTreewidthReduction.pdf 2010."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464827"},{"key":"e_1_3_2_2_8_1","volume-title":"Parameterized complexity theory","author":"Flum J.","year":"2006","unstructured":"J. Flum and M. Grohe . Parameterized complexity theory . Springer-Verlag New York Inc , 2006 . J. Flum and M. Grohe. Parameterized complexity theory. Springer-Verlag New York Inc, 2006."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167266"},{"key":"e_1_3_2_2_10_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/3-540-58201-0_92","volume-title":"Automata, Languages and Programming","author":"Garg N.","year":"1994","unstructured":"N. Garg , V. Vazirani , and M. Yannakakis . Multiway cuts in directed and node weighted graphs . In Automata, Languages and Programming , volume 820 of Lecture Notes in Computer Science , pages 487 -- 498 , 1994 . N. Garg, V. Vazirani, and M. Yannakakis. Multiway cuts in directed and node weighted graphs. In Automata, Languages and Programming, volume 820 of Lecture Notes in Computer Science, pages 487--498, 1994."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.03.005"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789707"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_28"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v46:3"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_3_2_2_17_1","unstructured":"D. Marx. Fixed parameter algorithms. http:\/\/www.cs.bme.hu\/$\\sim$dmarx\/papers\/marx-warsaw-fpt1 2009. D. Marx. Fixed parameter algorithms. http:\/\/www.cs.bme.hu\/$\\sim$dmarx\/papers\/marx-warsaw-fpt1 2009."},{"key":"e_1_3_2_2_18_1","volume-title":"STACS","author":"Marx D.","year":"2010","unstructured":"D. Marx , B. O'Sullivan , and I. Razgon . Treewidth reduction for constrained separation and bipartization problems . In STACS , 2010 . D. Marx, B. O'Sullivan, and I. Razgon. Treewidth reduction for constrained separation and bipartization problems. In STACS, 2010."},{"key":"e_1_3_2_2_19_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/978-3-642-04128-0_58","volume-title":"ESA","author":"Marx D.","year":"2009","unstructured":"D. Marx and I. Razgon . Constant ratio fixed-parameter approximation of the edge multicut problem . In ESA , volume 5757 of Lecture Notes in Computer Science , pages 647 -- 658 . Springer , 2009 . D. Marx and I. Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem. In ESA, volume 5757 of Lecture Notes in Computer Science, pages 647--658. Springer, 2009."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"crossref","unstructured":"D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. http:\/\/arxiv.org\/abs\/1010.3633 2010. D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. http:\/\/arxiv.org\/abs\/1010.3633 2010.","DOI":"10.1145\/1993636.1993699"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"Nagamochi H.","year":"2008","unstructured":"H. Nagamochi and T. Ibaraki . Algorithmic Aspects of Graph Connectivity . Cambridge University Press , New York, NY, USA , 1 edition, 2008 . H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York, NY, USA, 1 edition, 2008."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)","author":"Niedermeier R.","year":"2006","unstructured":"R. Niedermeier . Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications) . Oxford University Press , USA , March 2006 . R. Niedermeier. Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press, USA, March 2006."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993698","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:10Z","timestamp":1750244770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":23,"alternative-id":["10.1145\/1993636.1993698","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993698","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}