论文部分内容阅读
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 Cove