会议专题

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(万方平台首次上网日期,不代表论文的发表时间)