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.
Original language | English |
---|---|
Pages (from-to) | 672-686 |
Number of pages | 15 |
Journal | Applied Mathematics and Computation |
Volume | 197 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2008 Apr 1 |
All Science Journal Classification (ASJC) codes
- Computational Mathematics
- Applied Mathematics