Solving the Independent-set Problem in a DNA-Based Supercomputer Model

In this paper, it is demonstrated how the DNA (DeoxyriboNucleic Acid) operations presented by Adleman and Lipton can be used to develop the parallel genetic algorithm that solves the independent-set problem. The advantage of the genetic algorithm is the huge parallelism inherent in DNA based computi...

Full description

Saved in:
Bibliographic Details
Published in:Parallel processing letters 2005-12, Vol.15 (4), p.469-479
Main Authors: CHANG, WENG-LONG, GUO, MINYI, WU, JESSE
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, it is demonstrated how the DNA (DeoxyriboNucleic Acid) operations presented by Adleman and Lipton can be used to develop the parallel genetic algorithm that solves the independent-set problem. The advantage of the genetic algorithm is the huge parallelism inherent in DNA based computing. Furthermore, this work represents obvious evidence for the ability of DNA based parallel computing to solve NP-complete problems.
ISSN:0129-6264
1793-642X
DOI:10.1142/S0129626405002386