CASIA OpenIR  > 09年以前成果
A new DNA algorithm to solve graph coloring problem
Jiang, Xingpeng; Li, Yin; Meng, Ya; Meng, Dazhi
2007-06-01
发表期刊PROGRESS IN NATURAL SCIENCE
卷号17期号:6页码:733-738
文章类型Article
摘要Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNNA encoding molecules if the number of regions in a graph is R).
关键词Dna Computing Np-hard Problem Graph Coloring Problem
WOS标题词Science & Technology ; Technology
关键词[WOS]EVERY PLANAR MAP ; COMPUTER
收录类别SCI
语种英语
WOS研究方向Materials Science ; Science & Technology - Other Topics
WOS类目Materials Science, Multidisciplinary ; Multidisciplinary Sciences
WOS记录号WOS:000248557300018
引用统计
被引频次:2[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.ia.ac.cn/handle/173211/9485
专题09年以前成果
作者单位1.Beijing Univ Technol, Coll Appl Sci, Beijing 100022, Peoples R China
2.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100080, Peoples R China
3.Beijing Inst Technol, Sch Sci, Beijing 100081, Peoples R China
推荐引用方式
GB/T 7714
Jiang, Xingpeng,Li, Yin,Meng, Ya,et al. A new DNA algorithm to solve graph coloring problem[J]. PROGRESS IN NATURAL SCIENCE,2007,17(6):733-738.
APA Jiang, Xingpeng,Li, Yin,Meng, Ya,&Meng, Dazhi.(2007).A new DNA algorithm to solve graph coloring problem.PROGRESS IN NATURAL SCIENCE,17(6),733-738.
MLA Jiang, Xingpeng,et al."A new DNA algorithm to solve graph coloring problem".PROGRESS IN NATURAL SCIENCE 17.6(2007):733-738.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Jiang, Xingpeng]的文章
[Li, Yin]的文章
[Meng, Ya]的文章
百度学术
百度学术中相似的文章
[Jiang, Xingpeng]的文章
[Li, Yin]的文章
[Meng, Ya]的文章
必应学术
必应学术中相似的文章
[Jiang, Xingpeng]的文章
[Li, Yin]的文章
[Meng, Ya]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。