HUANG Yufang, XIAO Jianhua, JIANG Keqin, CHEN Zhihua. Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly[J]. Chinese Journal of Electronics, 2016, 25(2): 203-208. doi: 10.1049/cje.2016.03.002
Citation: HUANG Yufang, XIAO Jianhua, JIANG Keqin, CHEN Zhihua. Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly[J]. Chinese Journal of Electronics, 2016, 25(2): 203-208. doi: 10.1049/cje.2016.03.002

Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly

doi: 10.1049/cje.2016.03.002
Funds:  This work is supported by the National Natural Science Foundation of China (No.61402382, No.61373066, No.61370105, No.61202204), the Fundamental Research Funds for the Central Universities (No.2682014CX054), Postdoctoral Science Foundation of China (No.2012M521427), and Anhui Provincial Natural Science Foundation (No.1408085MF131).
More Information
  • Corresponding author: CHEN Zhihua (corresponding author) is an associate professor at Huazhong University of Science and Technology. Her research focuses on DNA nanotechnology and control theory. (Email:chenzhihua@hust.edu.cn)
  • Received Date: 2014-02-13
  • Rev Recd Date: 2014-09-19
  • Publish Date: 2016-03-10
  • 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.
  • loading
  • L. Pan, X. Zeng and X. Zhang, "Time-free spiking neural P systems", Neural Computation, Vol.23, No.5, pp.1320-1342, 2011.
    T. Song, L. Pan and G. P?un, "Asynchronous spiking neural P systems with local synchronization", Information Sciences, Vol.219, pp.197-207, 2013.
    X. Zhang, X. Zeng and L. Pan, "On string languages generated by spiking neural P systems with exhaustive use of rules", Natural Computing, Vol.7, No.4, pp.535-549, 2008.
    X. Zhang, X. Zeng and L. Pan, "On languages generated by asynchronous spiking neural P systems", Theoretical Computer Science, Vol.410, No.26, pp.2478-2488, 2009.
    L. Pan and X. Zeng, "Small universal spiking neural P systems working in exhaustive mode", IEEE Transactions on Nanobioscience, Vol.10, No.2, pp.99-105, 2011.
    L. Pan and M.J. Pérez-Jiménez, "Computational complexity of Tissue-like P systems", Journal of Complexity, Vol.26, No.3, pp. 296-315, 2010.
    L. Pan, G. P?un and M.J. Pérez-Jiménez, "Spiking neural P systems with neuron division and budding", Science China Information Sciences, Vol.54, No.8, pp.1596-1607, 2011.
    C. Dwyer and A. Lebeck, Introduction to DNA Self-assembled Computer Design, Artech House, INC, 2008.
    E. Winfree, "Algorithmic self-assembly of DNA", Ph.D. thesis, California Institute of Technology, 1998.
    H. Wang, "Dominoes and the AEA case of the decision problem", Proc. Symp. Math. Theory of Automata, Polytechnic Press, New York, pp.23-55, 1963.
    N. Kallenbach, R. Ma and N. Seeman, "An immobile nucleic acid junction constructed from oligonucleotides", Nature, Vol.305, No. 5937, pp.829-831, 1983.
    Y. Brun, "Nondeterministic polynomial time factoring in the tile assembly model", Theoretical Computer Science, Vol.395, No.1, pp.3-23, 2008.
    Y. Brun, "Solving NP-complete problems in the tile assembly model", Theoretical Computer Science, Vol.395, No.1, pp.31-46, 2008.
    Y. Brun, "Solving satisfiability in the tile assembly model with a constant-size tile set", Journal of Algorithms, Vol.63, No.4, pp.151-166, 2008.
    M. Lagoudakis and T. LaBean, "2D DNA Self-assembly for satisfiability", DIMACS Series in DISCRETE Mathematics and Theoretical Computer Science, pp.139-152, 2000.
    N. Jonoska and G. McColm, A Computational Model for Self-assembling Flexible Tiles, Berlin Heidelberg, Germany: Springer-Verlag, pp.142-156, 2005.
    Y. Huang, J. Xu and Z. Cheng, "Integer factorization based on the tile assembly model", Journal of Computational and Theoretical Nanoscience, Vol.8, No.1, pp.105-116, 2011.
    Y. Huang, J. Xu and Z. Cheng, "Algorithmic tile assembly for solution of the maximum clique problem", Journal of Computational and Theoretical Nanoscience, Vol.7, No.8, pp.1375-1385, 2010.
    Z. Cheng, "Arithmetic computation of multiplicative inversion and division in GF(2n) using self-assembly of DNA tiles", Journal of Computational and Theoretical Nanoscience, Vol.9, No.3, pp.336-346, 2012.
    Z. Cheng, "Nondeterministic algorithm for breaking Diffie-Hellman key exchange using self-assembly of DNA tiles", International Journal of Computers Communication and Control, Vol.7, No.4, pp.616-630, 2012.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (209) PDF downloads(683) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return