3D DNA Self-Assembly Model for Graph Vertex Coloring

doi:10.1166/jctn.2010.1355

CORC > 北京大学 > 信息科学技术学院

	3D DNA Self-Assembly Model for Graph Vertex Coloring
	Lin, Minqi ; Xu, Jin ; Zhang, Dafang ; Chen, Zhihua ; Zhang, Xuncai ; Cheng, Zhen ; Huang, Yufang ; Li, Yanbiao
刊名	journal of computational and theoretical nanoscience
	2010
关键词	Vertex Coloring 3D DNA Self-Assembly Non-Deterministic Algorithm DNA Computing COMPUTATION
DOI	10.1166/jctn.2010.1355
英文摘要	DNA self-assembly technology has brought novel inspirations to the development of DNA computing Diversified computational models based on DNA self-assembly have been used to solve various NP problems. In this paper, a 3D DNA self-assembly model is presented to solve the Graph Vertex Coloring problem. With the capacity of DNA molecules in massive parallel computation, the model can simulate a non-deterministic algorithm and solve the problem in linear time Theta(n) The number of distinct tiles used in the model is Theta(k(2)), where k is the size of the color set For the vertex 3-coloring problem, the model requires only 22 types of distinct tiles. Our work makes a significant attempt for exploring the computational power of 3D DNA self-assembly; Chemistry, Multidisciplinary; Nanoscience & Nanotechnology; Materials Science, Multidisciplinary; Physics, Applied; Physics, Condensed Matter; SCI(E); EI; 3; ARTICLE; 1; 246-253; 7
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/396023]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Lin, Minqi,Xu, Jin,Zhang, Dafang,et al. 3D DNA Self-Assembly Model for Graph Vertex Coloring[J]. journal of computational and theoretical nanoscience,2010.
APA	Lin, Minqi.,Xu, Jin.,Zhang, Dafang.,Chen, Zhihua.,Zhang, Xuncai.,...&Li, Yanbiao.(2010).3D DNA Self-Assembly Model for Graph Vertex Coloring.journal of computational and theoretical nanoscience.
MLA	Lin, Minqi,et al."3D DNA Self-Assembly Model for Graph Vertex Coloring".journal of computational and theoretical nanoscience (2010).