Improved Parameterized Algorithm for P2-Packing Problem
Jianxin Wang, Dan Ning, Qilong Feng, Jianer Chen · Journal of Software · 2009
P2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O*(25.301k)的参数算法,其核的大小为15k.通过对P2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O*(24.142k)的参数算法,大幅度改进了目前文献中的最好结果.;P2-Packing is a typical NP-hard problem. This paper provides a further study on the structures of the P2-packing problem, and proposes a kernelization algorithm that can obtain a kernel of size at most 7k, which greatly reduces the current best kernel 15k. Based on the kernelization algorithm, an improved parameterized algorithm with running time O*(24.142k) is also presented, which greatly improves the current best result O*(25.301k).