求有限集合覆盖的构造方法  

An Algorithm for Constructing Covers of Finite Sets

作　　者：吴寄语 邱伟星[1] 王蔚[1] 张迎周[1,2] 

机构地区：[1]南京邮电大学计算机学院,南京210046 [2]桂林电子科技大学广西可信软件重点实验室,广西桂林541004

出　　处：《大学数学》2017年第2期39-42,共4页College Mathematics

基　　金：广西可信软件重点实验室开放基金;江苏省"青蓝工程"中青年学术带头人项目

摘　　要：在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.In the field of approximation algorithms, Set Cover is one of the problems studied profoundly. This paper puts forward an algorithm for constructing covers of finite sets to solve another problem which is totally different to the classical SCP. And the completeness of the algorithm is proved. The algorithm is a straight forward, efficient and standard method for constructing set covering.

关 键 词：有限集合 NP问题 集合的划分 集合覆盖 

分 类 号：TN918.1[电子电信—通信与信息系统] O15[电子电信—信息与通信工程]