论文标题
空间有效的图核
Space-Efficient Graph Kernelizations
论文作者
论文摘要
令$ n $为参数化问题的大小，而参数为$ k $。我们提供用于反馈顶点集，路径收缩和群集编辑/删除的内核，其大小在$ k $中都是多项式的，并且可以在多项式时间内和$ o（\ rm {poly}（k）（k）\ log n）$位（工作记忆）进行计算。通过使用内核级联，我们使用$ o（\ rm {poly}（k）（k）\ log n）$位获得多项式时间中最著名的内核。
Let $n$ be the size of a parameterized problem and $k$ the parameter. We present kernels for Feedback Vertex Set, Path Contraction and Cluster Editing/Deletion whose sizes are all polynomial in $k$ and that are computable in polynomial time and with $O(\rm{poly}(k) \log n)$ bits (of working memory). By using kernel cascades, we obtain the best known kernels in polynomial time with $O(\rm{poly}(k) \log n)$ bits.
