Back to Search
Start Over
Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman–Lipton model
- Source :
-
Biosystems . Dec2003, Vol. 72 Issue 3, p263. 13p. - Publication Year :
- 2003
-
Abstract
- Adleman wrote the first paper in which it is shown that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the NP-complete Hamiltonian path problem (HPP). Lipton also demonstrated that Adleman’s techniques could be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem). In this paper, it is proved how the DNA operations presented by Adleman and Lipton can be used for developing DNA algorithms to resolving the set cover problem and the problem of exact cover by 3-sets. [Copyright &y& Elsevier]
- Subjects :
- *NP-complete problems
*HAMILTONIAN systems
*DNA
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 03032647
- Volume :
- 72
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Biosystems
- Publication Type :
- Academic Journal
- Accession number :
- 11467890
- Full Text :
- https://doi.org/10.1016/S0303-2647(03)00149-7