Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem
Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem
复制标题
子集反馈集问题和 S 循环打包问题的固定参数易处理性
DOI：
10.1016/j.jctb.2011.12.001
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Kawarabayashi and Y. Kobayashi
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi and Y. Kobayashi
在参数化复杂性的框架下，我们研究了以下众所周知的问题的推广：反馈集问题和循环填充问题。我们的问题设置是给定一个图和一个顶点集S，称为“终端”。我们在这里的目的是考虑以下问题：我们给出了两个问题的第一个固定参数算法。即;
We investigate generalizations of the following well-known problems in the framework of parameterized complexity: the feedback set problem and the cycle packing problem. Our problem setting is that we are given a graph and a vertex set S called “terminals”. Our purpose here is to consider the following problems: We give the first fixed parameter algorithms for the two problems. Namely;