Advanced Search
    Zhou Xu, Zhou Yantao, Ouyang Aijia, Li Kenli. An Efficient Tile Assembly Model for Maximum Clique Problem[J]. Journal of Computer Research and Development, 2014, 51(6): 1253-1262.
    Citation: Zhou Xu, Zhou Yantao, Ouyang Aijia, Li Kenli. An Efficient Tile Assembly Model for Maximum Clique Problem[J]. Journal of Computer Research and Development, 2014, 51(6): 1253-1262.

    An Efficient Tile Assembly Model for Maximum Clique Problem

    • The tile self-assembly model has attracted enormous attention from the scientist because of its characters which are nanoscale properties, self-assembly, programmable and so on. However, the exponential explosion problem of solution space has already become the great obstacle to its further development. Hence, a novel efficient tile self-assembly model for maximum clique problem is proposed in this paper. The new model is composed of TileDual subsystem, initial configuration subsystem and detecting subsystem. For the sake of reducing the solution space, the concept of TileDual molecular and the enlighten strategy are introduced to the TileDual subsystem. Based on the three subsystems above, a new algorithm for the maximum clique problem is proposed. Compared with the proposed tile self-assembly models for the maximum clique problem, the solution space in our model can reduce from 2n0 to 1.712n-2n and the successive rate can improve from 0.5n0 to 0.5n-0.57n, where n0, n represent the vertex number of the graph G and G0 respectively. So the proposed model not only has the advantages of tile self-assembly model, but also needs much less solution space and can get much higher successive rate.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return