| P2-Packing问题参数算法的改进 |
| |
| 引用本文： | 王建新,宁 丹,冯启龙,陈建二.P2-Packing问题参数算法的改进[J].软件学报,2008,19(11):2879-2886. |
| |
| 作者姓名： | 王建新 宁 丹 冯启龙 陈建二 |
| |
| 作者单位： | 中南大学 信息科学与工程学院,湖南 长沙 410083;中南大学 信息科学与工程学院,湖南 长沙 410083;中南大学 信息科学与工程学院,湖南 长沙 410083;中南大学 信息科学与工程学院,湖南 长沙 410083 |
| |
| 基金项目： | 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 (长江学者和创新团队发展计划) |
| |
| 摘 要： | P2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O*(25.301k)的参数算法,其核的大小为15k.通过对P2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O*(24.142k)的参数算法,大幅度改进了目前文献中的最好结果.
|
| 关 键 词： | P2-packing 核心化 参数算法 |
| 收稿时间： | 9/2/2007 12:00:00 AM |
| 修稿时间： | 1/8/2008 12:00:00 AM |
Improved Parameterized Algorithm for P2-Packing Problem |
| |
| WANG Jian-Xin,NING Dan,FENG Qi-Long and CHEN Jian-Er.Improved Parameterized Algorithm for P2-Packing Problem[J].Journal of Software,2008,19(11):2879-2886. |
| |
| Authors: | WANG Jian-Xin NING Dan FENG Qi-Long and CHEN Jian-Er |
| |
| Abstract: | 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). |
| |
| Keywords: | P2-packing kernelization parameterized algorithm |
|
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
