Parallelism in the theoretical computation mainly depends on the particular paradigm or computational environment considered, and its importance has been confirmed with the emergence of each novel computing technique. Programmable tile assembly is a novel computing technique to tackle computationally difficult problems, in which computing time grows exponentially corresponding to problematic size. The Maximum independent set (MIS) problem is a typical nondeterministic polynomial problem, which is often associated with strategy applications. In this paper, a novel approach dealing with the MIS problem is proposed based on the abstract tile assembly model, which is believed to be better than the conventional silicon-based computing in solving the same problem. The method can get the solutions of the MIS problem in θ(m+ n) time complexity based on θ(mn) distinct tile types.
展开▼
