Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
复制标题
次指数时间和固定参数可处理性：利用小型化映射
DOI：
10.1093/logcom/exn029
复制
发表时间：
2007-09
影响因子：
0.7
通讯作者：
Flum, Joerg
中科院分区：
文献类型：
--
作者：
Chen, Yijia;Flum, Joerg
最近引入了一个映射M，即所谓的小型化映射，并证明了M忠实地将次指数参数化复杂性转化为（无界）参数化复杂性[2]。我们确定的原像下M的各种（类）的问题，并表明它们符合自然reparameterizations考虑到解决这些问题所需的非确定性的数量。
Recently a mapping M, the so-called miniaturization mapping, has been introduced and it has been shown that M faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity [2]. We determine the preimages under M of various (classes of) problems and show that they coincide with natural reparameterizations which take into account the amount of nondeterminism needed to solve them.
登录
查看更多内容
DOI：
10.1145/263661.263664
发表时间：
1997-05
期刊：
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems
影响因子：
--
作者：
C. Papadimitriou;M. Yannakakis
通讯作者：
C. Papadimitriou;M. Yannakakis
DOI：
10.1016/s0022-0000(70)80041-1
发表时间：
1970-10
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
J. Doner
通讯作者：
J. Doner
DOI：
10.1007/3-540-29953-x
发表时间：
2006
期刊：
--
影响因子：
--
作者：
J. Flum;Martin Grohe
通讯作者：
J. Flum;Martin Grohe
影响因子：
1
作者：
Chen, J;Chor, B;Xia, G
通讯作者：
Xia, G
DOI：
--
发表时间：
2003
期刊：
--
影响因子：
--
作者：
通讯作者：
--