ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

A Surface-Based DNA Algorithm for the Perfect Matching Problem

Chen Zhiping, Li Xiaolong, Wang Lei, Lin Yaping, and Cai Lijun   

  1. (College of Computer and Communications, Hunan University, Changsha 410082)
  • Online:2005-07-15

Abstract: Using the method of fluorescence labeling, a new DNA algorithm of the perfect matching problem based surface is presented in this paper. By fixing the DNA molecules of the solution space on the solid carrier, all solutions of the perfect matching problem by the biochemical actions can be acquired. Compared with other surface-based DNA algorithms for maximal matching problem, this algorithm can precisely get the edges existing in any perfect matching without using observation, and the edge order hasn't influence on the solution generating process. Therefore, the new algorithm can get better performance.

Key words: DNA computing, solution space, maximum matching, perfect matching problem