| P2-Packing问题参数算法的改进 |
| |
| 引用本文： | 王建新,宁丹,冯启龙,陈建二. P2-Packing问题参数算法的改进[J]. 软件学报, 2008, 19(11) |
| |
| 作者姓名： | 王建新 宁丹 冯启龙 陈建二 |
| |
| 作者单位： | 中南大学,信息科学与工程学院,湖南,长沙,410083 |
| |
| 基金项目： | 60773111，the Program for New century Excellent Talents in Univcrsity 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 |
| |
| 摘 要： | P_2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O(2~(5.301k))的参数算法,其核的大小为15k.通过对P_2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O(2~(4.142k))的参数算法,大幅度改进了目前文献中的最好结果.
|
| 关 键 词： | P_2-packing 核心化 参数算法 |
Improved Parameterized Algorithm for P2-Packing Problem |
| |
| WANG Jian-Xin,NING Dan,FENG Qi-Long,CHEN Jian-Er. Improved Parameterized Algorithm for P2-Packing Problem[J]. Journal of Software, 2008, 19(11) |
| |
| Authors: | WANG Jian-Xin NING Dan FENG Qi-Long CHEN Jian-Er |
| |
| Abstract: | P_2-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'(25'3~1k). |
| |
| Keywords: | P_2-packing kernelization parameterized algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
