基于DNA自组装模型解决图的最小顶点覆盖问题  

Minimum Vertex Cover Problem Solution Based On Self-assembly Model of DNA

作　　者：郭洪敏[1] 殷志祥[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《安徽理工大学学报（自然科学版）》2015年第3期17-20,共4页Journal of Anhui University of Science and Technology:Natural Science

基　　金：国家自然科学基金资助项目(61170172)

摘　　要：在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。On the basis of analysis of the characteristics of the minimum vertex cover problem,taking a graph with 5 vertices as an example the minimum vertex cover problem was transformed into a problem of satisfiability,to simplify the operation of the problem. Then according to spontaneity and parallelism of DNA self- assembly and other advantages,by establishing self- assembly model of DNA the satisfiability problem was solved. Thus the minimum vertex cover problem was solved. Compared with the traditional algorithm,in the studied algorithm only gel electrophoresis technology is applied,which greatly reduces the difficulty of the operation and error.

关 键 词：最小顶点覆盖 DNA自组装模型 可满足性问题 

分 类 号：O157.5[理学—数学]