论文标题
最佳大小的问题内核，用于$ d $ - 线性时间和空间中的设置
Optimal-size problem kernels for $d$-Hitting Set in linear time and space
论文作者
论文摘要
使用二次大小的数据结构（尚未完全初始化）的$ d $ hitting设置的已知线性时间内元素保证线性最差的运行时间。摆脱了这种数据结构，我们表明，对于$ d $ hitting set的渐近最佳尺寸$ o（k^d）$的问题内核可以在线性时间和空间中计算。此外，我们通过实验性地比较了$ d $键入的线性时间内元素相互设置，并将由于weihe引起的经典数据减少算法进行比较。
The known linear-time kernelizations for $d$-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size $O(k^d)$ for $d$-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for $d$-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.
