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

Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing

作　　者：周康[1] 同小军[1] 刘文斌[2] 许进[2] 

机构地区：[1]武汉工业学院数理科学系,武汉430023 [2]华中科技大学控制科学与工程系

出　　处：《计算机工程》2008年第4期40-41,44,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60403002);浙江省自然科学基金资助项目(ZJNSF-Y105654)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]