| A surface-based DNA algorithm for the minimal vertex cover problem |
| |
| 作者姓名： | PAN Linqiang XU Jin and LIU Yachun |
| |
| 作者单位： | Department of Control Science and Engineering，Huazhong University of Science and Technology，Wuhan 430074，China; Department of Mathematics and Physics，Institute of Engineering and Technology，Nanhua University，Hengyang 421001，China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China (Grant Nos. 60103021 and 60174047)，China Postdoctoral Science Foundation |
| |
| 摘 要： | Abstract DNA computing was proposed for solving a class of intractable computational problems, of which the computing timewill grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase itsreliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique hasnot been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal ver-tex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the abilityof surface-based DNA computing in solving NP-complete problems.
|
A surface-based DNA algorithm for the minimal vertex cover problem |
| |
| PAN Linqiang,XU Jin and LIU Yachun.A surface-based DNA algorithm for the minimal vertex cover problem[J].Progress in Natural Science,2003,13(1). |
| |
| Authors: | PAN Linqiang XU Jin LIU Yachun |
| |
| Abstract: | DNA computing was proposed for solving a class of intractable computational problems, of which the computing time will grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase its reliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique has not been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal vertex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the ability of surface-based DNA computing in solving NP-cornplete problems. |
| |
| Keywords: | DNA computing NP-complete problem minimal vertex cover problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
