| A new DNA algorithm to solve graph coloring problem |
| |
| 作者姓名： | Jiang Xingpeng Li Yin Meng Ya and Meng Dazhi |
| |
| 作者单位： | 1. National Laboratory of Pattern Recognition,Institute of Automation, Chinese Academy of Sciences, Beijing 100080， China; 2. College of Applied Sciences, Beijing University of Technology, Beijing 100022， China; 3. School of Science, Beijing Institute of Technology, Beijing 100081， China |
| |
| 摘 要： | 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 DNA encoding molecules if the number of regions in a graph is R).
|
A new DNA algorithm to solve graph coloring problem |
| |
| Authors: | Jiang Xingpeng Li Yin Meng Ya and Meng Dazhi |
| |
| Abstract: | 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 DNA encoding molecules if the number of regions in a graph is R). |
| |
| Keywords: | DNA computing NP-hard problem graph coloring problem |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《自然科学进展》浏览原始摘要信息 |
| 点击此处可从《自然科学进展》下载免费的PDF全文 |
