Streaming Kernelization
Streaming Kernelization
复制标题
流式内核化
DOI：
10.1007/978-3-662-44465-8_24
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
Stefan Fafianie;Stefan Kratsch
核化是组合困难问题的一种形式化处理方法。我们修改了核化的标准定义，它允许任何多项式时间算法进行预处理，相反，要求预处理在流设置中运行，并使用实例(x，k)上的内存位。我们在这个新的设置中得到了几个结果，这取决于允许这样的流内核化在输入上传递的次数。Edge支配设置被证明是一个有趣的例子，因为它没有单遍内核化，但在输入上的两次内核化足以匹配最佳标准内核化的界限。
Kernelization is a formalization of preprocessing for combinatorially hard problems. We modify the standard definition for kernelization, which allows any polynomial-time algorithm for the preprocessing, by requiring instead that the preprocessing runs in a streaming setting and usesbits of memory on instances (x,k). We obtain several results in this new setting, depending on the number of passes over the input that such a streaming kernelization is allowed to make.Edge Dominating Setturns out as an interesting example because it has no single-pass kernelization but two passes over the input suffice to match the bounds of the best standard kernelization.
有根 k 叶分支问题的线性时间核化
DOI：
10.1016/j.dam.2015.04.028
发表时间：
2013
期刊：
Revue d'epidemiologie et de sante publique
影响因子：
--
作者：
Frank Kammer
通讯作者：
Frank Kammer
影响因子：
1.1
作者：
René van Bevern
通讯作者：
René van Bevern
DOI：
10.1007/978-3-642-28050-4_15
发表时间：
2011-09
期刊：
--
影响因子：
--
作者：
T. Hagerup
通讯作者：
T. Hagerup