Turing kernelization for finding long paths and cycles in restricted graph classes

详细信息    查看全文

• 作者：Bart M.P. Jansen ^{B.M.P.Jansen@tue.nl}
• 关键词：Parameterized complexity ; Turing kernelization ; k-Path ; Preprocessing
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：85
• 期：Complete
• 页码：18-37
• 全文大小：755 K
• 卷排序：85

文摘

Polynomial-size Turing kernels are developed for k-Path and k-Cycle. These problems do not have polynomial-size traditional kernels. We introduce the Decompose–Query–Reduce framework for preprocessing. For bounded-degree graphs, colored k-Path is more difficult than normal k-Path.