Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4636379 | Applied Mathematics and Computation | 2007 | 5 Pages |
Abstract
Many combinatorial optimization problems are known to be NP-complete. A common point of view is that finding fast algorithms for such problems using a polynomial number of processors is unlikely. However, facts of this kind are usually established for “worst” case situations, and in practice many instances of NP-complete problems are successfully solved in polynomial time by such traditional combinatorial optimization techniques such as dynamic programming, branch-and-bound.New opportunities for an effective solution of combinatorial problems emerged with the advent of parallel machines. In this paper, we describe an algorithm which generates an optimal solution for the 0/1 integer knapsack problem on DNA computing.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Majid Darehmiraki, Hasan Mishmast Nehi,