A DNA Algorithm for the maximal matching problem

Wenxia Li; E. M. Patrikeev; Dongmei Xiao

doi:10.1134/S0005117915100070

A DNA Algorithm for the maximal matching problem

Wenxia Li^*
, E. M. Patrikeev
, Dongmei Xiao

^*Corresponding author for this work

School of Mathematical Sciences

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

8 Scopus citations

Abstract

We propose a procedure for solving the classical discrete extremal maximal matching problem with the Adleman–Lipton model as the computational architecture. We show that for an undirected graph with n edges the solution can be obtained in O(n²) steps.

Original language	English
Pages (from-to)	1797-1802
Number of pages	6
Journal	Automation and Remote Control
Volume	76
Issue number	10
DOIs	https://doi.org/10.1134/S0005117915100070
State	Published - 1 Oct 2015

Access to Document

10.1134/S0005117915100070

Cite this

@article{2e2f3611ef064a408a272f676c38a0cb,

title = "A DNA Algorithm for the maximal matching problem",

abstract = "We propose a procedure for solving the classical discrete extremal maximal matching problem with the Adleman–Lipton model as the computational architecture. We show that for an undirected graph with n edges the solution can be obtained in O(n2) steps.",

author = "Wenxia Li and Patrikeev, \{E. M.\} and Dongmei Xiao",

note = "Publisher Copyright: {\textcopyright} 2015, Pleiades Publishing, Ltd.",

year = "2015",

month = oct,

day = "1",

doi = "10.1134/S0005117915100070",

language = "英语",

volume = "76",

pages = "1797--1802",

journal = "Automation and Remote Control",

issn = "0005-1179",

publisher = "Pleiades Publishing",

number = "10",

}

TY - JOUR

T1 - A DNA Algorithm for the maximal matching problem

AU - Li, Wenxia

AU - Patrikeev, E. M.

AU - Xiao, Dongmei

PY - 2015/10/1

Y1 - 2015/10/1

N2 - We propose a procedure for solving the classical discrete extremal maximal matching problem with the Adleman–Lipton model as the computational architecture. We show that for an undirected graph with n edges the solution can be obtained in O(n2) steps.

AB - We propose a procedure for solving the classical discrete extremal maximal matching problem with the Adleman–Lipton model as the computational architecture. We show that for an undirected graph with n edges the solution can be obtained in O(n2) steps.

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

U2 - 10.1134/S0005117915100070

DO - 10.1134/S0005117915100070

M3 - 文章

AN - SCOPUS:84944916783

SN - 0005-1179

VL - 76

SP - 1797

EP - 1802

JO - Automation and Remote Control

JF - Automation and Remote Control

IS - 10

ER -

A DNA Algorithm for the maximal matching problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this