计算机工程 ›› 2008, Vol. 34 ›› Issue (4): 40-41.doi: 10.3969/j.issn.1000-3428.2008.04.014

• 博士论文 • 上一篇    下一篇

基于闭环DNA计算的最大独立集问题的算法

周 康1,2,同小军1,2,刘文斌2,3,许 进2   

  1. (1. 武汉工业学院数理科学系,武汉 430023;2. 华中科技大学控制科学与工程系,武汉 430074;3. 温州大学计算机科学与工程学院,温州 325027)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20

Algorithm of Maximum Independent Set ProblemBased on Closed Circle DNA Computing

ZHOU Kang1,2, TONG Xiao-jun1,2, LIU Wen-bin2,3, XU Jin2   

  1. (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)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20

摘要: 提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。

关键词: 闭环DNA计算模型, 最大独立集问题, 删除实验, 电泳实验

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.

Key words: model of closed circle DNA computing, maximum independent set problem, delete experiment, electrophoresis experiment

中图分类号: