| New algorithms for some NP-optimization problems by DNA computing |
| |
| 作者姓名： | QU Huiqin ZHU Hong PENG Chao |
| |
| 作者单位： | Department of Computer Science, Fudan University, Shanghai 200433, China,Department of Computer Science, Fudan University, Shanghai 200433, China,Department of Computer Science, Fudan University, Shanghai 200433, China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China (Grant Nos. 69973013 and 69673038) |
| |
| 摘 要： | There are lots of DNA computation models now. The model developed by Martyn Amos' group is special in its error-resistant property, but unfortunately, its computational power is limited and cannot solve optimization problems efficiently. In this paper, some new methods have been introduced to enlarge the computational power of this model. And based on these new methods, several DNA algorithms have been designed to solve some NP-optimization problems such as minimal vertex cover, maximal clique and MAX-3SAT.
|
| 关 键 词： | NP-optimization algorithms DNA computing |
New algorithms for some NP-optimization problems by DNA computing |
| |
| QU Huiqin,ZHU Hong,PENG Chao.New algorithms for some NP-optimization problems by DNA computing[J].Progress in Natural Science,2002,12(6):459-462. |
| |
| Authors: | QU Huiqin ZHU Hong PENG Chao |
| |
| Institution: | Department of Computer Science, Fudan University, Shanghai 200433, China |
| |
| Abstract: | There are lots of DNA computation models now. The model developed by Martyn Amos' group is special in its error-resistant property, but unfortunately, its computational power is limited and cannot solve optimization problems efficiently. In this paper, some new methods have been introduced to enlarge the computational power of this model. And based on these new methods, several DNA algorithms have been designed to solve some NP-optimization problems such as minimal vertex cover, maximal clique and MAX-3SAT. |
| |
| Keywords: | NP-optimization algorithms DNA computing |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
