Solving the Independent-set Problem in a DNA-Based Supercomputer Model
作者： WENG-LONG CHANG , MINYI GUO , JESSE WU
DOI: 10.1142/S0129626405002386
关键词: Parallel algorithm 、 Parallel genetic algorithm 、 NP-complete 、 Theoretical computer science 、 A-DNA 、 Supercomputer 、 Genetic algorithm 、 Mathematics 、 Parallelism (grammar) 、 Independent set
摘要: In this paper, it is demonstrated how the DNA (DeoxyriboNucleic Acid) operations presented by Adleman and Lipton can be used to develop parallel genetic algorithm that solves independent-set problem. The advantage of huge parallelism inherent in based computing. Furthermore, work represents obvious evidence for ability computing solve NP-complete problems.
sci-hub.se 参考文章(4)
L. Adleman, Molecular computation of solutions to combinatorial problems Science. ,vol. 266, pp. 1021- 1024 ,(1994) , 10.1126/SCIENCE.7973651
Qi Ouyang, Peter D Kaplan, Shumao Liu, Albert Libchaber, DNA Solution of the Maximal Clique Problem Science. ,vol. 278, pp. 446- 449 ,(1997) , 10.1126/SCIENCE.278.5337.446
R. Lipton, DNA solution of hard computational problems Science. ,vol. 268, pp. 542- 545 ,(1995) , 10.1126/SCIENCE.7725098
Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, DNA Computing Springer Berlin Heidelberg. ,(1998) , 10.1007/978-3-662-03563-4