3D DNA Self-Assembly Model for Graph Vertex Coloring | |
Zhang DF(张德富) | |
2010 | |
关键词 | Vertex Coloring 3D DNA Self-Assembly Non-Deterministic Algorithm DNA Computing |
英文摘要 | 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 |
语种 | 英语 |
内容类型 | 期刊论文 |
源URL | [http://dspace.xmu.edu.cn/handle/2288/70936] ![]() |
专题 | 信息技术-已发表论文 |
推荐引用方式 GB/T 7714 | Zhang DF. 3D DNA Self-Assembly Model for Graph Vertex Coloring[J],2010. |
APA | 张德富.(2010).3D DNA Self-Assembly Model for Graph Vertex Coloring.. |
MLA | 张德富."3D DNA Self-Assembly Model for Graph Vertex Coloring".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论