Solving maximum cut problems in the Adleman-Lipton model

Dongmei Xiao; Wenxia Li; Zhizhou Zhang; Lin He

doi:10.1016/j.biosystems.2005.06.009

Solving maximum cut problems in the Adleman-Lipton model

Dongmei Xiao
, Wenxia Li^*
, Zhizhou Zhang
, Lin He

^*Corresponding author for this work

School of Mathematical Sciences

Shanghai Jiao Tong University

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

22 Scopus citations

Abstract

In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.

Original language	English
Pages (from-to)	203-207
Number of pages	5
Journal	BioSystems
Volume	82
Issue number	3
DOIs	https://doi.org/10.1016/j.biosystems.2005.06.009
State	Published - Dec 2005

Keywords

Adleman-Lipton model
DNA computing
Maximum cut problem
NP-complete problem

Access to Document

10.1016/j.biosystems.2005.06.009

Cite this

@article{01c6eff62d784a0aae2c417485f3a823,

title = "Solving maximum cut problems in the Adleman-Lipton model",

abstract = "In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.",

keywords = "Adleman-Lipton model, DNA computing, Maximum cut problem, NP-complete problem",

author = "Dongmei Xiao and Wenxia Li and Zhizhou Zhang and Lin He",

year = "2005",

month = dec,

doi = "10.1016/j.biosystems.2005.06.009",

language = "英语",

volume = "82",

pages = "203--207",

journal = "BioSystems",

issn = "0303-2647",

publisher = "Elsevier Ireland Ltd",

number = "3",

}

TY - JOUR

T1 - Solving maximum cut problems in the Adleman-Lipton model

AU - Xiao, Dongmei

AU - Li, Wenxia

AU - Zhang, Zhizhou

AU - He, Lin

PY - 2005/12

Y1 - 2005/12

N2 - In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.

AB - In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.

KW - Adleman-Lipton model

KW - DNA computing

KW - Maximum cut problem

KW - NP-complete problem

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

U2 - 10.1016/j.biosystems.2005.06.009

DO - 10.1016/j.biosystems.2005.06.009

M3 - 文章

C2 - 16236426

AN - SCOPUS:27844585880

SN - 0303-2647

VL - 82

SP - 203

EP - 207

JO - BioSystems

JF - BioSystems

IS - 3

ER -

Solving maximum cut problems in the Adleman-Lipton model

Abstract

Keywords

Access to Document

Other files and links

Cite this