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

Sun-Yuan Hsieh, Ming Yu Chen

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

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 languageEnglish
Pages (from-to)672-686
Number of pages15
JournalApplied Mathematics and Computation
Volume197
Issue number2
DOIs
Publication statusPublished - 2008 Apr 1

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers'. Together they form a unique fingerprint.

Cite this