Three Dimensional DNA Self-Assembly Model for the Minimum Vertex Cover Problem

摘要：

DNA self-assembly technology has brought novel inspiration to the development of DNA computing. Diversified computational models based on DNA selfassembly have been used to solve various NF problems. In this paper, a three-dimensional (3D) DNA selfassembly model is presented to solve the minimum vertex cover problem. With the capacity of DNA molecules in massive parallel computation, the model can simulate a non-deterministic algorithm and solve the problem in polynomial time. Meanwhile, the computation space of the model is O(n3) and the number of distinct tiles is 0(1).

关键词： Minimum Vertex Cover DNA Self-Assembly Non-Deterministic Algorithm DNA Computing

作者: Xuncai Zhang Wenjun Song Ruili Fan Guangzhao Cui

作者单位: College of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou, College of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou

会议类型: 国际会议

会议名称: 2011 Fourth International Symposium on Computational Interlligence and Design 第四届计算智能与设计国际会议 ISCID 2011

会议地点: 杭州

会议语种:英文

页码: 348-351

在线出版日期: 2011-10-28（万方平台首次上网日期，不代表论文的发表时间）