| 基于闭环DNA计算的最大独立集问题的算法 |
| |
| 引用本文： | 周康,同小军,刘文斌,许进. 基于闭环DNA计算的最大独立集问题的算法[J]. 计算机工程, 2008, 34(4): 40-41 |
| |
| 作者姓名： | 周康 同小军 刘文斌 许进 |
| |
| 作者单位： | 武汉工业学院数理科学系,武汉,430023;华中科技大学控制科学与工程系,武汉,430074;华中科技大学控制科学与工程系,武汉,430074;温州大学计算机科学与工程学院,温州,325027;华中科技大学控制科学与工程系,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金 , 浙江省自然科学基金 |
| |
| 摘 要： | 提出闭环DNA计算模型及其基本生化实验，给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中，提出并实现了用删除实验直接构造所有最大独立集的构想，即通过多次删除实验使顶点集合逐步满足独立集的要求，最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验，实现简捷、可靠。
|
| 关 键 词： | 闭环DNA计算模型 最大独立集问题 删除实验 电泳实验 |
| 文章编号： | 1000-3428（2008）04-0040-02 |
| 收稿时间： | 2007-03-28 |
| 修稿时间： | 2007-03-28 |
Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing |
| |
| ZHOU Kang,TONG Xiao-jun,LIU Wen-bin,XU Jin. Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing[J]. Computer Engineering, 2008, 34(4): 40-41 |
| |
| Authors: | ZHOU Kang TONG Xiao-jun LIU Wen-bin XU Jin |
| |
| Affiliation: | (1. Department of Mathematics and Physics, Wuhan Polytechnic University,Wuhan 430023 ;2. Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074; 3. College of Computer Science and Engineering, Wenzhou University, Wenzhou 325027) |
| |
| Abstract: | This paper brings forward model of closed circle DNA computing and its basic bio-chemistry experiments. An algorithm with closed circle DNA of the maximum independent set problem is put forward. In the algorithm, an idea that all maximum independent sets are formed straightway by deleting experiment is put forward and realized, that condition of maximum independent is satisfied gradually by doing time after time delete experiments. Only using basic bio-chemistry experiment-delete experiment, the algorithm is simple and credible. |
| |
| Keywords: | model of closed circle DNA computing maximum independent set problem delete experiment electrophoresis experiment |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
|
