A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers

Sun-Yuan Hsieh, Ming Yu Chen

研究成果: Article同行評審

22 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)672-686
頁數15
期刊Applied Mathematics and Computation
197
發行號2
DOIs
出版狀態Published - 2008 四月 1

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

指紋 深入研究「A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers」主題。共同形成了獨特的指紋。

引用此