Set Cover和Hitting Set问题的研究进展  

Set Cover and Hitting Set:A Survey

作　　者：李绍华[1,2] 王建新[1] 冯启龙[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]广东商学院信息学院,广州510320

出　　处：《计算机科学》2009年第10期1-4,15,共5页Computer Science

基　　金：国家973前期研究专项(2008CB317107);国家自然科学基金(60433020;60773111);新世纪优秀人才支持计划(NCET-05-0683);国家教育部创新团队资助项目(IRT0661)资助

摘　　要：Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。Set cover and hitting set problems are two important W[2]-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 recent research results about these problems. The paper proved the computational complexity levels of （k, h）-set Cover and （k, d）-Set Cover. Finally, the main points are concluded and some future research issues are outlined.

关 键 词：集合覆盖 撞碰集 近似算法 固定参数可解 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]