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
国际会议
杭州
英文
348-351
2011-10-28(万方平台首次上网日期,不代表论文的发表时间)