Linear Solving of Maximum Set Packing Problem by DNA Computing

Adleman showed that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the Hamiltonian path problem (HPP) [1]. Lipton also demonstrated that Adleman’s techniques could be used to solve the Satisfiability problem (SAT) [2]. Recently, DNA computing has considerable attention as one of non-silicon based computing. Watson-Crick complementarity and massive parallelism are two important features of DNA computing. By using these features, one can solve an NP-hard problem, which usually needs exponential time on a silicon-based computers, in a polynomial number of steps with DNA molecules. DNA algorithms typically solve problems by initially assembling large data sets as input and then eliminating undesirable solutions. Adleman and Lipton introduced the following operations that each of them can be done in O(1) by DNA based computer. In this paper we use them to develop a linear time DNA algorithm for solving maximum set packing problem. The problem is very important in real world problem such as channel assignment problem [3], though it is an NP-hard problem and one can not solve it efficiently by silicon computers