Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly
Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly
复制标题
DOI：
10.1049/cje.2016.03.002
复制
发表时间：
2016-03
影响因子：
1.2
通讯作者：
Yufang Huang;Jian-hua Xiao;Keqin Jiang;Zhihua Chen
中科院分区：
文献类型：
--
作者：
Yufang Huang;Jian-hua Xiao;Keqin Jiang;Zhihua Chen
理论计算中的并行性主要取决于所考虑的特定范式或计算环境，其重要性随着每一种新的计算技术的出现而得到证实。可编程瓦片组装是一种新的计算技术，用于解决计算困难的问题，其中计算时间随问题大小呈指数增长。最大独立集（MIS）问题是一个典型的非确定性多项式问题，经常与策略应用相关联。本文提出了一种基于抽象瓦片装配模型的管理信息系统问题的新方法，该方法在解决相同问题方面优于传统的基于硅的计算方法。该方法可以根据θ(mn)种不同的瓦片类型，得到时间复杂度为θ(m + n)的MIS问题的解。
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.