碰集

碰集（hitting set）是离散数学的集合论中的概念。如果集合S与集合簇C中的每个集合都存在着非空交集，那么集合S是集合簇C的碰集。如果在不破坏碰集的前提下，集合S中的元素都无法移除，那么S被称为极小碰集。计算碰集的传统算法有 HS-Tree ，HS-DAG ，HST-Tree ，BHS-Tree，SE-Tree 等等，在此基础上，学者们又陆续提出了一些新的算法。