A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
复制标题
（太阳）花的捷径：对数空间或线性时间中的内核
DOI：
10.1007/978-3-662-48054-0_25
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
S. Fafianie;Stefan Kratsch
我们研究了如果将核化算法限制在对数空间中，是否可以得到核化结果。这种对核化的限制源于这样一个问题，即通过简单和/或局部约简规则进行预处理可以获得什么结果。我们找到了\(d\) -命中集(k)、\(d\) -集打包(k)、边缘支配集(k)的核化，以及图中的许多命中和打包问题，每个问题都在对数空间中运行。另外，我们回到线性时间核化的问题。对于\(d\) -hitting set(k), van Bevern [Algorithmica(2014)]给出了一个线性时间核。我们给出了一个更简单的过程，并在大小范围内节省了一个大的常数因子。进一步，我们证明了我们可以得到\(d\) -set packing(k)的线性时间核。
We investigate whether kernelization results can be obtained if we restrict kernelization algorithms to run in logarithmic space. This restriction for kernelization is motivated by the question of what results are attainable for preprocessing via simple and/or local reduction rules. We find kernelizations for \(d\)-hitting set( k ), \(d\)-set packing( k ), edge dominating set( k ), and a number of hitting and packing problems in graphs, each running in logspace. Additionally, we return to the question of linear-time kernelization. For \(d\)-hitting set( k ) a linear-time kernel was given by van Bevern [Algorithmica (2014)]. We give a simpler procedure and save a large constant factor in the size bound. Furthermore, we show that we can obtain a linear-time kernel for \(d\)-set packing( k ).
影响因子：
1.1
作者：
René van Bevern
通讯作者：
René van Bevern