A linear kernel for the complementary maximal strip recovery problem

作者：

Highlights：

• We obtain a tight linear kernel for the NP-complete problem CMSR.

• We first try to obtain a direct weak kernel (or search space) for the solution.

• Different from many FPT algorithms, most of our rules are not local.

• We show once more that a direct weak kernel can be converted to a kernel.

摘要

•We obtain a tight linear kernel for the NP-complete problem CMSR.•We first try to obtain a direct weak kernel (or search space) for the solution.•Different from many FPT algorithms, most of our rules are not local.•We show once more that a direct weak kernel can be converted to a kernel.

论文关键词：Maximum strip recovery,FPT algorithm,Kernelization

论文评审过程：Received 7 September 2012, Revised 26 January 2014, Accepted 4 March 2014, Available online 14 March 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.03.005