计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2009年
10期
1-4,15
,共5页
李绍华%王建新%冯启龙%陈建二
李紹華%王建新%馮啟龍%陳建二
리소화%왕건신%풍계룡%진건이
集合覆盖%撞碰集%近似算法%固定参数可解
集閤覆蓋%撞踫集%近似算法%固定參數可解
집합복개%당팽집%근사산법%고정삼수가해
Set Cover和Hitting Set问题是两个重要的W[2]完全问题.Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用.在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点.首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,h)-Set Cover问题的复杂性证明.最后总结全文并提出进一步研究的方向.
Set Cover和Hitting Set問題是兩箇重要的W[2]完全問題.Set Cover問題在大規模集成電路設備的測試和人員調度等領域有著廣汎的應用,Hitting Set問題在生物計算等領域有著重要的應用.在引入參數計算和複雜性理論後,Set Cover和Hitting Set問題再次成為研究的熱點.首先介紹Set Cover和Hitting Set的各種分類問題及其定義,併對各種分類問題的計算複雜性和相關算法的研究進展加以分析總結,給齣(k,h)-Set Cover和(k,h)-Set Cover問題的複雜性證明.最後總結全文併提齣進一步研究的方嚮.
Set Cover화Hitting Set문제시량개중요적W[2]완전문제.Set Cover문제재대규모집성전로설비적측시화인원조도등영역유착엄범적응용,Hitting Set문제재생물계산등영역유착중요적응용.재인입삼수계산화복잡성이론후,Set Cover화Hitting Set문제재차성위연구적열점.수선개소Set Cover화Hitting Set적각충분류문제급기정의,병대각충분류문제적계산복잡성화상관산법적연구진전가이분석총결,급출(k,h)-Set Cover화(k,h)-Set Cover문제적복잡성증명.최후총결전문병제출진일보연구적방향.
