Computer Science ›› 2009, Vol. 36 ›› Issue (10): 1-4.
Next Articles
LI Shao-hua,WANG Jinn-xin,FENG Qi-long,CHEN Jinn-cr
Online:
Published:
Abstract: Set cover and hitting set problems are two important W[2]-complete problems. Set cover problem is applied widely in the testing of VI_SI 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 fo-cused 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. hhe 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 arc outlined.
Key words: Set cover, Hitting set, Approximation algorithm, Fixed parameter tractable
LI Shao-hua,WANG Jinn-xin,FENG Qi-long,CHEN Jinn-cr. Set Cover and Hitting Set: A Survey[J].Computer Science, 2009, 36(10): 1-4.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2009/V36/I10/1
Cited