| 最大独立集问题的表面计算模型 |
| |
| 引用本文： | 杨燕,殷志祥,崔建中,马莹.最大独立集问题的表面计算模型[J].科技信息,2007(30). |
| |
| 作者姓名： | 杨燕 殷志祥 崔建中 马莹 |
| |
| 作者单位： | 安徽理工大学电气系 安徽淮南232001 |
| |
| 摘 要： | DNA计算是解决一类难于计算问题的一种新方法,最大独立集问题是一个著名的NP完全问题,最大团问题及最小覆盖问题等价于最大独立集问题。本文中,我们尝试将最大独立集转化为0-1规化问题,利用0-1规化问题的表面计算模型求解最大独立集。本文充分说明了NP-完全问题可以相互转化的性质。
|
| 关 键 词： | DNA计算 0-1规化问题 最大独立集 最大团 最小顶点覆盖 |
Surface-based computing model of Maximum Independent Set problem |
| |
| Yangyan,Yinzhixiang,cuijianzhong,Mayin.Surface-based computing model of Maximum Independent Set problem[J].Science,2007(30). |
| |
| Authors: | Yangyan Yinzhixiang cuijianzhong Mayin |
| |
| Institution: | Yangyan1,Yinzhixiang2,cuijianzhong2,Mayin2 |
| |
| Abstract: | DNA computing is a novel method of solving a class of intractable computational problems,in which maximum Independent Set problem (MIS) is a well-known NP-complete problem. Maximum Clique and Minimum Vertex Covering problem is equivalent to Maximum Independent Set problem. In this paper,we explore solving Maximum Independent Set problem by transforming it into equivalent 0-1 programming problem,and utilizing the surface computing model for 0-1 programming problem. The proposed method demonstrates universal nature of NP-complete problem. |
| |
| Keywords: | DNA computing 0-1 programming problem Maximum Independent Set Maximum Clique Minimum Vertex Covering |
| 本文献已被 CNKI 等数据库收录！ |
|
