This article is cited in 7 papers

System Analysis and Operations Research

A DNA algorithm for the maximal matching problem

Li Wenxia^a, E. M. Patrikeev^a, Xiao Dongmei<sup>b

a</sup> East China Normal University, Shanghai, China
^b Jiao Tong University, Shanghai, China

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^2)$ steps.

Presented by the member of Editorial Board: V. I. Gurman

Received: 20.01.2015

 English version: Automation and Remote Control, 2015, 76:10, 1797–1802

Bibliographic databases:

• 
• 
•