title: Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model.
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.
authors.affiliation: Department of Information Management, Southern Taiwan University of Technology, 701 ROC, Tainan, Taiwan. changwl@csie.ncku.edu.tw
authors.forename: Weng Long
authors.initials: WL
authors.lastname: Chang
authors.forename: Minyi
authors.initials: M
authors.lastname: Guo
mesh_terms: D000465:Algorithms; D004247:DNA / Q000737:chemistry; D008954:Models, Biological; D008957:Models, Genetic; D008958:Models, Molecular; D008962:Models, Theoretical; D012984:Software; D013223:Statistics as Topic / Q000379:methods*
chemical_list: D004247:DNA