A molecular solution for minimum vertex cover problem in tile assembly model

作者：Wu, Fan; Li, Kenli^*; Sallam, Ahmed; Zhou, Xu

来源：Journal of Supercomputing, 2013, 66(1): 148-169.

DOI：10.1007/s11227-013-0892-0

• Tile assembly model
• Minimum vertex cover problem
• DNA computing

Self-assembly is a generalization of the crystal growth, which has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computation. In the same context, tile assembly model is a highly distributed parallel model of natural self-assembly. In this paper, we propose a tile assembly system to tackle a well-known NP-complete problem known as Minimum Vertex Cover problem. The proposed algorithm requires I similar to(nxm) types of tiles, and each parallel assembly executes in a linear time, where n is the number of vertices and m is the number of edges. Furthermore, the experimental results proved the simplicity and the efficiency of the proposed algorithm to solve the Minimum Vertex Cover, and reduce the overall complexity to find the solution.

• 出版日期2013-10
• 单位湖南大学