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

第34卷第4期 计算机工程 2008年2月 2008 、bt。34 No．4 ComputerEngineering February looo—3428(20鸺)0‘卜砌Mo_．02A TP301．6 ·博士论：文· 文章编号t 文献标识码l 中啊分类号l 基于闭环DNA计算的最大独立集问题的算法 月康L2，同小军n，刘文斌Ⅺ，许进2 (1．武汉工业学院数理科学系，武汉430023；2．华中科技大学控制科学与工程系，武汉430074； 3．温州大学计算机科学与工程学院，温州325027) 摘要：提出闭环DNA计算模型及其基本生化实验，给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中，提出并实现了用 删除实验直接构造所有最大独立集的构想，即通过多次删除实验使顶点集合逐步满足独立集的要求，最后达到最大独立集。该方法使得算 法的设计筒单明了。算法仅用到基本的删除实验，实现简捷、可靠。 · 关键词：闭环DNA计算模型；最大独立集问题；删除实验；电泳实验 Problem ofMaximum Set Algorithm Independent BasedonClosedCircleDNA Computing ZHOU Jin2 Kang址，TONGXiao-junL2，LIUWen．bin2’3，XU ofMathematicsand Polytechnic 430023； (1．Department Physics，WuhanUniversity，Wuhan ofControlScienceand ofScienceand University Technology,Wuhan430074； 2．Department Engineering，Huazhong of Scienceand 325027) 3．CollegeComputer Engineering，WenzhouUniversity,Wenzhou anditsbasic withclosed This forwardmodelofclosedcircleDNA experiments．An IAbstmctl computing bio-chemistry algorithm paperbrings set is forward．Inthe ideathatallm般imum setsaleformed circleDNAofthemaximum algorithm，an independent indep