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

Sun-Yuan Hsieh; Ming Yu Chen

doi:10.1016/j.amc.2007.08.005

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

Sun-Yuan Hsieh, Ming Yu Chen

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	672-686
Number of pages	15
Journal	Applied Mathematics and Computation
Volume	197
Issue number	2
DOIs	https://doi.org/10.1016/j.amc.2007.08.005
Publication status	Published - 2008 Apr 1

All Science Journal Classification (ASJC) codes

Computational Mathematics
Applied Mathematics

Access to Document

10.1016/j.amc.2007.08.005

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

@article{33935682e5304be98413098ab00c562f,

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

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.",

author = "Sun-Yuan Hsieh and Chen, {Ming Yu}",

year = "2008",

month = apr,

day = "1",

doi = "10.1016/j.amc.2007.08.005",

language = "English",

volume = "197",

pages = "672--686",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

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

AU - Hsieh, Sun-Yuan

AU - Chen, Ming Yu

PY - 2008/4/1

Y1 - 2008/4/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=39449100009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39449100009&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2007.08.005

DO - 10.1016/j.amc.2007.08.005

M3 - Article

AN - SCOPUS:39449100009

VL - 197

SP - 672

EP - 686

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

IS - 2

ER -