Implementation of Maximum Independent Set Problem by Algorithmic Tile Self-Assembly

摘要: The maximum independent set problem is a classic combinational optimization problem. Recently, algorithmic tile self-assembly considered as promising technique in nanotechnology. In this work, we show how the process used to implement including three small systems: nondeterministic guess system, AND operation system and comparing system. Our method can be successfully performed ¦¨(mn) steps parallely at very low cost, here n m number of vertices edges given graph.