| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
A Polynomial Kernel For Multicut In Trees
Abstract : The MULTICUT IN TREES problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer k, whether there exists a set of k edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer. They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows. We show that MULTICUT IN TREES has a polynomial kernel.
https://hal.inria.fr/inria-00359171
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Friday, February 6, 2009 - 10:47:34 AM
Last modification on : Friday, October 22, 2021 - 3:07:28 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:57:11 PM
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Friday, February 6, 2009 - 10:47:34 AM
Last modification on : Friday, October 22, 2021 - 3:07:28 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:57:11 PM
Files
Bousquet_new.pdf
Files produced by the author(s)