| Set Cover和Hitting Set问题的研究进展 |
| |
| 引用本文： | 李绍华,王建新,冯启龙,陈建二.Set Cover和Hitting Set问题的研究进展[J].计算机科学,2009,36(10):1-4. |
| |
| 作者姓名： | 李绍华 王建新 冯启龙 陈建二 |
| |
| 作者单位： | 1. 中南大学信息科学与工程学院,长沙410083;广东商学院信息学院,广州510320
2. 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家973前期研究专项(2008CB317107);;国家自然科学基金(60433020,60773111);;新世纪优秀人才支持计划(NCET-05-0683);;国家教育部创新团队资助项目(IRT0661)资助 |
| |
| 摘 要： | Set Cover和Hitting Set问题是两个重要的W2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。
|
| 关 键 词： | 集合覆盖 撞碰集 近似算法 固定参数可解 |
| 收稿时间： | 2008/11/11 0:00:00 |
| 修稿时间： | 2009/1/17 0:00:00 |
Set Cover and Hitting Set: A Survey |
| |
| LI Shao-hu,WANG Jinn-xin,FENG Qi-long,CHEN Jinn-cr.Set Cover and Hitting Set: A Survey[J].Computer Science,2009,36(10):1-4. |
| |
| Authors: | LI Shao-hu WANG Jinn-xin FENG Qi-long CHEN Jinn-cr |
| |
| Affiliation: | School of Information Science and Engineering;Central South University;Changsha 410083;China;Information School;Guangdong University of Commercial Studies;Guangzhou 510320;China |
| |
| Abstract: | Set cover and hitting set problems are two important W2]-complete problems.Set cover problem is applied widely in the testing of VLSI devices and crew scheduling.Hitting set problem has important applications in biological computation.In the parameterized computation and complexity theory,Set Cover and hitting set problems have been focused on.This paper firstly introduced the categories and definitions of set cover and hitting set problems,then analyzed and summarized the computational complexity and the ... |
| |
| Keywords: | Set cover Hitting set Approximation algorithm Fixed parameter tractable |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
