Algorithmic Tile Self-Assembly for Solving the Maximal Matching Problem

被引：0
作者：
Cheng, Zhen [1 ]
Huang, Yufang [2 ]
Xiao, Jianhua [3 ]
机构：
[1] College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou
[2] College of Mathematics, Southwest Jiaotong University, Chengdu
[3] The Research Center of Logistics Nankai University, Tianjin
来源：
Advances in Intelligent Systems and Computing | 2013年 / 212卷
基金：
中国国家自然科学基金;
关键词：
Algorithmic; Maximal matching problem; Self-assembly; Tile;
D O I：
10.1007/978-3-642-37502-6_100
中图分类号：
学科分类号：
摘要：
The maximal matching problem is a classic combinatorial optimization problem. Recently, computation by algorithmic tile self-assembly is proved to be a promising technique in nanotechnology, and this computational model is also demonstrated to be Turing universal. In this paper, the process of tile self-assembly model which is used to solve the maximal matching problem is shown including three operations: nondeterministic guess operation, AND operation and comparing operation. Our method can be performed this problem in Θ(mn) steps, here m and n is the number of edges and vertices of the given graph respectively. © Springer-Verlag Berlin Heidelberg 2013.
引用
收藏
页码：845 / 854
页数：9
相关论文
共 15 条
  • [1] Adleman L.M., Molecular computation of solutions to combinatorial problems, Science, 266, pp. 1021-1024, (1994)
  • [2] Pan L.Q., Liu G.W., Xu J., Solid phase based DNA solution of the coloring problem, Prog Nat Sci, 14, pp. 104-107, (2004)
  • [3] Pan L.Q., Perez-Jimenez M.J., Computational complexity of tissue-like P systems, J Complex, 26, pp. 296-315, (2010)
  • [4] Seeman N.C., DNA nanotechnology: Novel DNA constructions, Annu Rev Biophy Biomol Struct, 27, pp. 225-248, (1998)
  • [5] Mao C., Sun W., Seeman N.C., Designed two dimensional DNA Holliday junction arrays visualized by atomic force microscopy, J Am Chem Soc, 121, pp. 5437-5443, (1999)
  • [6] Barish R., Rothemund P.W., Winfree E., Two computational primitives for algorithmic self-assembly: Copying and counting, Nano Lett, 12, pp. 2586-2592, (2005)
  • [7] Lo P.K., Metera K.L., Sleiman H.F., Self-assembly of three-dimensional DNA nanostructures and potential biological applications, Curr Opin Chem Biol, 14, pp. 597-607, (2010)
  • [8] Wang H., Proving theorems by pattern recognition. I, Bell Syst Tech J, 40, pp. 1-42, (1961)
  • [9] Winfree E., Algorithmic Self-assembly of DNA, (1998)
  • [10] Rothemund P., Winfree E., The program-size complexity of self-assembled squares, Proceedings of the Annual ACM Symposium On Theory of Computing, pp. 459-468, (2000)
12