欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
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.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：