CASIA OpenIR  > 09年以前成果
A new DNA algorithm to solve graph coloring problem
Jiang, Xingpeng; Li, Yin; Meng, Ya; Meng, Dazhi
AbstractUsing 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).
KeywordDna Computing Np-hard Problem Graph Coloring Problem
WOS HeadingsScience & Technology ; Technology
Indexed BySCI
WOS Research AreaMaterials Science ; Science & Technology - Other Topics
WOS SubjectMaterials Science, Multidisciplinary ; Multidisciplinary Sciences
WOS IDWOS:000248557300018
Citation statistics
Document Type期刊论文
Affiliation1.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
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Jiang, Xingpeng]'s Articles
[Li, Yin]'s Articles
[Meng, Ya]'s Articles
Baidu academic
Similar articles in Baidu academic
[Jiang, Xingpeng]'s Articles
[Li, Yin]'s Articles
[Meng, Ya]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Jiang, Xingpeng]'s Articles
[Li, Yin]'s Articles
[Meng, Ya]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.