| 求有限集合覆盖的构造方法 |
| |
| 引用本文： | 吴寄语,邱伟星,王蔚,张迎周. 求有限集合覆盖的构造方法[J]. 大学数学, 2017, 33(2): 39-42. DOI: 10.3969/j.issn.1672-1454.2017.02.006 |
| |
| 作者姓名： | 吴寄语 邱伟星 王蔚 张迎周 |
| |
| 作者单位： | 1. 南京邮电大学计算机学院,南京,210046;2. 南京邮电大学计算机学院,南京210046;桂林电子科技大学广西可信软件重点实验室,广西桂林541004 |
| |
| 基金项目： | 广西可信软件重点实验室开放基金，江苏省“青蓝工程”中青年学术带头人项目 |
| |
| 摘 要： | 在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.
|
| 关 键 词： | 有限集合 NP问题 集合的划分 集合覆盖 |
An Algorithm for Constructing Covers of Finite Sets |
| |
| WU Ji-yu,QIN Wei-xing,WANG Wei,ZHANG Ying-zhou. An Algorithm for Constructing Covers of Finite Sets[J]. College Mathematics, 2017, 33(2): 39-42. DOI: 10.3969/j.issn.1672-1454.2017.02.006 |
| |
| Authors: | WU Ji-yu QIN Wei-xing WANG Wei ZHANG Ying-zhou |
| |
| Abstract: | 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. |
| |
| Keywords: | finite sets NP problems set dividing set covering |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
