Journals Information
Computer Science and Information Technology Vol. 1(2), pp. 90 - 96
DOI: 10.13189/csit.2013.010203
Reprint (PDF) (316Kb)
Using Parallel Filtering Algorithms to Solve the 0-1 Knapsack Problem on DNA-based Computing
Sientang Tsai*
Department of Information Management, Southern Taiwan University of Science and Technology, Taiwan
ABSTRACT
It is shown first by Adleman that deoxyribonucleic acid (DNA) strands could be employed towards calculating solution to an instance of the NP-complete Hamiltonian Path Problem (HPP). Lipton also demonstrated that Adleman鈥檚 techniques could be used to solve the satisfiability (SAT) problem. In this paper, it is demonstrated how the DNA operations presented by Adleman and Lipton can be used to develop the DNA-based algorithm for solving the 0-1 Knapsack Problem.
KEYWORDS
DNA-based Computing, NP-complete Problems, 0-1 Knapsack Problem
Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Sientang Tsai , "Using Parallel Filtering Algorithms to Solve the 0-1 Knapsack Problem on DNA-based Computing," Computer Science and Information Technology, Vol. 1, No. 2, pp. 90 - 96, 2013. DOI: 10.13189/csit.2013.010203.
(b). APA Format:
Sientang Tsai (2013). Using Parallel Filtering Algorithms to Solve the 0-1 Knapsack Problem on DNA-based Computing. Computer Science and Information Technology, 1(2), 90 - 96. DOI: 10.13189/csit.2013.010203.