Set Packing问题的研究进展

• 作者: 冯启龙 王建新 陈建二 马振宇
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: Set Packing问题 NP难问题 复杂性理论 参数计算
• 年，卷（期）: 2007,（9）
• 页码范围: 12-15,22
• 页数: 5页
• 分类号: TP3
• 字数: 7983字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2007.09.003

摘要

Set Packing问题起源于分割问题的应用,是在强约束条件对元素进行划分.在复杂性理论中,此问题是一类重要的NP难问题,被广泛应用于调度、代码优化和生物信息学等领域.特别是在参数计算理论产生后,此问题再次成为研究的热点问题.依据所研究问题的差异,本文将Set Packing问题分成5类,并给出了具体的定义.在此基础上,分别介绍了求解这5类问题的相关算法,着重分析和比较了参数算法中所运用的各项技术,并提出了该问题算法研究的一些发展方向.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	冯启龙	中南大学信息科学与工程学院	11	38	4.0	6.0
4	马振宇	中南大学信息科学与工程学院	2	11	2.0	2.0