摘要
P_2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O(2^(5.301k))的参数算法,其核的大小为15k.通过对P_2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O(2^(4.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^＊（2^4.142k） is also presented, which greatly improves the current best result O^＊（2^5.301K）.
出处
《软件学报》
EI
CSCD
北大核心
2008年第11期2879-2886,共8页
Journal of Software
基金
Supported by the National Natural Science Foundation of China under Grant Nos.60433020
60773111(国家自然科学基金)
the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683(新世纪优秀人才支持计划)
the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No.IRT0661(长江学者和创新团队发展计划)
