Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4634613 | Applied Mathematics and Computation | 2008 | 15 Pages |
Abstract
Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the graph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Sun-Yuan Hsieh, Ming-Yu Chen,