A DNA algorithm for the graph coloring problem

Wenbin Liu; Fengyue Zhang; Jin Xu

doi:10.1021/ci025546e

A DNA algorithm for the graph coloring problem

Wenbin Liu^*, Fengyue Zhang, Jin Xu

^*Corresponding author for this work

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

26 Citations (Scopus)

Abstract

A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.

Original language	English
Pages (from-to)	1176-1178
Number of pages	3
Journal	Journal of Chemical Information and Computer Sciences
Volume	42
Issue number	5
DOIs	https://doi.org/10.1021/ci025546e
Publication status	Published - Sept 2002
Externally published	Yes

Access to Document

10.1021/ci025546e

Cite this

@article{4592821a14834af8aeeb01068df9b91f,

title = "A DNA algorithm for the graph coloring problem",

abstract = "A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.",

author = "Wenbin Liu and Fengyue Zhang and Jin Xu",

year = "2002",

month = sep,

doi = "10.1021/ci025546e",

language = "English",

volume = "42",

pages = "1176--1178",

journal = "Journal of Chemical Information and Computer Sciences",

issn = "0095-2338",

publisher = "American Chemical Society",

number = "5",

}

TY - JOUR

T1 - A DNA algorithm for the graph coloring problem

AU - Liu, Wenbin

AU - Zhang, Fengyue

AU - Xu, Jin

PY - 2002/9

Y1 - 2002/9

N2 - A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.

AB - A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.

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

U2 - 10.1021/ci025546e

DO - 10.1021/ci025546e

M3 - Article

C2 - 12377006

AN - SCOPUS:0036708523

SN - 0095-2338

VL - 42

SP - 1176

EP - 1178

JO - Journal of Chemical Information and Computer Sciences

JF - Journal of Chemical Information and Computer Sciences

IS - 5

ER -

A DNA algorithm for the graph coloring problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this