A DNA procedure for solving the shortest path problem

Zhaocai Wang; Dongmei Xiao; Wenxia Li; Lin He

doi:10.1016/j.amc.2006.05.061

A DNA procedure for solving the shortest path problem

Zhaocai Wang, Dongmei Xiao, Wenxia Li, Lin He

School of Mathematical Sciences

Shanghai Jiao Tong University

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.

Original language	English
Pages (from-to)	79-84
Number of pages	6
Journal	Applied Mathematics and Computation
Volume	183
Issue number	1
DOIs	https://doi.org/10.1016/j.amc.2006.05.061
State	Published - 1 Dec 2006

Keywords

Adleman-Lipton model
DNA computing
NP-complete problem
The shortest path problem

Access to Document

10.1016/j.amc.2006.05.061

Cite this

@article{7f352430776a4624b7430345f937b90c,

title = "A DNA procedure for solving the shortest path problem",

abstract = "In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.",

keywords = "Adleman-Lipton model, DNA computing, NP-complete problem, The shortest path problem",

author = "Zhaocai Wang and Dongmei Xiao and Wenxia Li and Lin He",

year = "2006",

month = dec,

day = "1",

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

language = "英语",

volume = "183",

pages = "79--84",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - A DNA procedure for solving the shortest path problem

AU - Wang, Zhaocai

AU - Xiao, Dongmei

AU - Li, Wenxia

AU - He, Lin

PY - 2006/12/1

Y1 - 2006/12/1

N2 - In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.

AB - In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.

KW - Adleman-Lipton model

KW - DNA computing

KW - NP-complete problem

KW - The shortest path problem

UR - https://www.scopus.com/pages/publications/33845394633

U2 - 10.1016/j.amc.2006.05.061

DO - 10.1016/j.amc.2006.05.061

M3 - 文章

AN - SCOPUS:33845394633

SN - 0096-3003

VL - 183

SP - 79

EP - 84

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 1

ER -

A DNA procedure for solving the shortest path problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this