Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly

HUANG Yufang; XIAO Jianhua; JIANG Keqin; CHEN Zhihua

doi:10.1049/cje.2016.03.002

Volume 25 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(2): 203-208

HUANG Yufang, XIAO Jianhua, JIANG Keqin, et al., “Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 203-208, 2016, doi: 10.1049/cje.2016.03.002

Citation:

HUANG Yufang, XIAO Jianhua, JIANG Keqin, et al., “Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 203-208, 2016, doi: 10.1049/cje.2016.03.002

Citation:

PDF( 359 KB)

Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly

doi: 10.1049/cje.2016.03.002

1.
School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China;
2.
School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China;
3.
Research Center of Logistics, Nankai University, Tianjin 300071, China;
4.
School of Computer and Information, Anqing Normal University, Anqing 246133, China

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

Abstract

Abstract

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.
- Molecular computing,
- Tile assembly model,
- Maximum independent set (MIS),
- Self-assembly,
- Parallel computing

FullText(HTML)

References(20)

References

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(2ⁿ) 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.

Relative Articles

Supplements(0)

Cited By

Proportional views