Volume 31 Issue 2
Mar.  2022
Turn off MathJax
Article Contents
CUI Jianzhong, YIN Zhixiang, TANG Zhen, YANG Jing. Probe Machine Based Computing Model for Maximum Clique Problem[J]. Chinese Journal of Electronics, 2022, 31(2): 304-312. doi: 10.1049/cje.2020.00.293
Citation: CUI Jianzhong, YIN Zhixiang, TANG Zhen, YANG Jing. Probe Machine Based Computing Model for Maximum Clique Problem[J]. Chinese Journal of Electronics, 2022, 31(2): 304-312. doi: 10.1049/cje.2020.00.293

Probe Machine Based Computing Model for Maximum Clique Problem

doi: 10.1049/cje.2020.00.293
Funds:  This work was supported by the National Natural Science Foundation of China (62072296,61702008) and Natural Science Foundation of Anhui University (KJ2019A0538)
More Information
  • Author Bio:

    was born in 1973, Ph.D. candidate. He received postgraduate degree from Anhui University of Science and Technology. His currently research interests include the combination and optimization, and DNA computing. (Email: 983505198@qq.com)

    (corresponding author), Professor, was born in 1966. He received Ph.D. degree of Huazhong University of Science and Technology. His research interests include the graph theory, combinatorial optimization, DNA computing, and protein structure prediction. He currently serves as the Director of Development and Planning, Anhui University of Science and Technology. (Email: zxyin66@163.com)

    was born in 1994. He is a Ph.D. student. He received his master degree from Anhui University of Science and Technology. His currently research interests include the combination and optimization, and DNA computing. (Email: 983505198@qq.com)

    was born in 1980. She received Ph.D. degree from Anhui University of Science and Technology. Her research interests include the graph, combinatorial optimization, and big data. (Email: jyangh82@163.com)

  • Received Date: 2020-09-11
  • Accepted Date: 2021-09-29
  • Available Online: 2021-11-30
  • Publish Date: 2022-03-05
  • Probe machine (PM) is a recently reported mathematic model with massive parallelism. Herein, we presented searching the maximum clique of an undirected graph with six vertices. We constructed data library containing n sublibraries, each sublibrary corresponded to a vertex in the given graph. Then, probe library according to the induced subgraph was designed in order to search and generate all maximal cliques. Subsequently, we performed probe operation, and all maximal cliques were generated in parallel. The advantages of the proposed model lie in two aspects. On one hand, solution to NP-complete problem is generated in just one step of probe operation rather than found in vast solution space. On the other hand, the proposed model is highly parallel. The work demonstrates that PM is superior to TM in terms of searching capacity when tackling NP-complete problem.
  • loading
  • [1]
    J. Xie, W Kong, L Pang, et al., “Staggered grid scheme for the FFT-based methods,” Chinese Journal of Electronics, vol.28, no.5, pp.1066–1072, 2019. doi: 10.1049/cje.2019.06.002
    [2]
    N. Zhang and T. Zhang, “Recurrent neural networks for computing the moore-penrose inverse with momentum learning,” Chinese Journal of Electronics, vol.29, no.6, pp.1039–1045, 2020. doi: 10.1049/cje.2020.02.005
    [3]
    L. Yang, G Hu, C Zhang, et al., “Solving structured nonlinear programming based on CPU-GPU collaborative parallel interior point algorithm,” Chinese Journal of Electronics, vol.47, no.2, pp.382–389, 2019.
    [4]
    M. Yue and B. Bai, “Design and implementation of DSP system for motor FOC algorithm,” Chinese Journal of Electronics, vol.48, no.10, pp.2041–2046, 2020.
    [5]
    J. Liu, Y. Ge, M. Tian, et al., “ZYNQ-based reconfigurable convolutional neural network accelerator,” Chinese Journal of Electronics, vol.49, no.4, pp.729–735, 2021.
    [6]
    N. Hou, F. He, Y. Zhou, et al., “An efficient GPU-based parallel tabu search algorithm for hardware/software co-design,” Frontiers of Computer Science, vol.14, no.5, pp.1–18, 2020.
    [7]
    Y. Zhou, F. He, N. Hou, et al., “Parallel ant colony optimization on multi-core SIMD CPUs,” Future Generation Computer Systems, vol.79, no.2, pp.473–487, 2018.
    [8]
    Y. Zhou, F. He, and Y. Qiu, “Accelerating image convolution filtering algorithms on integrated CPU-GPU architectures,” Journal of Electronic Imaging, vol.27, article no.033002, 2018. doi: 10.1117/1.JEI.27.3.033002
    [9]
    Y. Zhou, F. He, and Y. Qiu, “Dynamic strategy based parallel ant colony optimization on GPUs for TSPs,” Science China Information Sciences, vol.60, article no.068102, 2017. doi: 10.1007/s11432-015-0594-2
    [10]
    D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proc. of the Royal Society of London A, vol.400, no.1818, pp.97–117, 1985. doi: 10.1098/rspa.1985.0070
    [11]
    M. Muller, “Strongly universal quantum turing machines and invariance of Kolmogorov complexity,” IEEE Trans. on Information Theory, vol.54, no.2, pp.763–780, 2008. doi: 10.1109/TIT.2007.913263
    [12]
    Frank Tabakin, “Model dynamics for quantum computing,” Annals of Physics, vol.383, pp.33–78, 2017. doi: 10.1016/j.aop.2017.04.013
    [13]
    W. S. Mcculloch and W. Pitts, “A logical calculus of the ideas immanent in nervous activity,” Bulletin of Mathematical Biology, vol.5, pp.115–133, 1943. doi: 10.1007/BF02478259
    [14]
    Z. Aram, S. Jafari, J. Ma, et al., “Using chaotic artificial neural networks to model memory in the brain,” Communications in Nonlinear Science and Numerical Simulation, vol.44, pp.449–459, 2017. doi: 10.1016/j.cnsns.2016.08.025
    [15]
    M. Ranjbar, S. Effati, and S. M. Miri, “An artificial neural network for solving quadratic zero-one programming problems,” Neurocomputing, vol.235, pp.192–198, 2017.
    [16]
    L. Adleman, “Molecular computation of solutions to combinatorial problems,” Science, vol.266, no.5187, pp.1021–1024, 1994. doi: 10.1126/science.7973651
    [17]
    Z. X. Yin, J. Z. Cui, and J. Yang, “Integer programming problem based on plasmid DNA computing model,” Chinese Journal of Electronics, vol.26, no.6, pp.1284–1288, 2017. doi: 10.1049/cje.2017.07.013
    [18]
    T. Song, P. Zheng, W. M. L. Dennis, et al., “Design of logic gates using spiking neural P systems with homogeneous neurons and astrocytes-like control,” Information Sciences, vol.372, pp.380–391, 2016.
    [19]
    X. Wang, T. Song, F. Gong, et al., “On the computational power of spiking neural P systems with self-organization,” Scientific Reports, vol.6, no.1, pp.27624–27639, 2016. doi: 10.1038/srep27624
    [20]
    H. Peng, J. Yang, J. Wang, et al., “Spiking neural P systems with multiple channels,” Neural Networks, vol.95, pp.66–71, 2017.
    [21]
    J. Xu, “Probe machine,” IEEE Transactions on Neural Networks & Learning Systems, vol.27, no.7, pp.1405–1416, 2016.
    [22]
    R. M. Karp. “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, edit., New York: Plenum Press, pp.88−103, 1972.
    [23]
    C. Godsil and B. Rooney, “Hardness of computing clique number and chromatic number for Cayley graphs,” European Journal of Combinatorics, vol.62, pp.147–166, 2017.
    [24]
    R. D. Luce and A. D. Perry, “A method of matrix analysis of group structure,” Psychometrika, vol.14, no.2, pp.95–116, 1949. doi: 10.1007/BF02289146
    [25]
    F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry, vol.20, no.3, pp.205–215, 1957. doi: 10.2307/2785673
    [26]
    D. E. Knuth, The Art of Computer Programming, 1st ed., Addison-Wesley Professional, 2011.
    [27]
    A. H. Land, “An automatic method of solving discrete programming problem,” Econometrica, vol.28, no.3, pp.497–520, 1960. doi: 10.2307/1910129
    [28]
    P. S. Segundo, A. Lopez, and P. M. Pardalos, “A new exact maximum clique algorithm for large and massive sparse graphs,” Computers & Operations Research, vol.66, pp.81–94, 2016.
    [29]
    C. M. Li, H. Jiang, and F. Manyà, “On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem,” Computers & Operations Research, Vol.84, DOI: 10.1016/j.cor.2017.02.017, 2017.
    [30]
    R. Kopf and G. Ruhe, “A computational study of the weighted independent set problem for general graphs,” Foundations of Control Engineering, vol.12, no.4, pp.167–180, 1987.
    [31]
    S. Zhang, W. Jing, Q. Wu, et al., “A fast genetic algorithm for solving the maximum clique problem,” 2014 10th International Conference on Natural Computation, IEEE, Xiamen, China, DOI: 10.1109/ICNC.2014.697593, 2014.
    [32]
    C. Friden, A. Hertz, and D. Werra, “Stabulus: A technique for finding stable sets in large graphs with tabu search,” Computing, vol.42, no.1, pp.35–44, 1989. doi: 10.1007/BF02243141
    [33]
    F. Ma, J. K. Hao, and Y. Wang, “An effective iterated tabu search for the maximum bisection problem,” Computers & Operations Research, vol.81, pp.78–89, 2017.
    [34]
    A. K. Jagota and K. W. Regan, “Performance of MAX-CLIQUE Approximation heuristics under description-length weighted distributions,” available at: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2FA485973535F33AA6535F861791FA33?doi=10.1.1.32.6486&rep=rep1&type=pdf, 1992.
    [35]
    G. Yang and J. Yi, “Delayed chaotic neural network with annealing controlling for maximum clique problem,” Neurocomputing, vol.127, pp.114–123, 2014.
    [36]
    Q. Ouyang, “DNA solution of the maximal clique problem,” Science, vol.278, no.5337, pp.446–449, 1997. doi: 10.1126/science.278.5337.446
    [37]
    T. Head, G. Rozenberg, R. S. Bladergroen, et al., “Computing with DNA by operating on plasmids,” Biosystems, vol.57, no.2, pp.87–93, 2000. doi: 10.1016/S0303-2647(00)00091-5
    [38]
    LI Ken-Li, ZHOU Xu, and ZOU Shu-Ting, “Improved volume molecular solutions for the maximum clique problem on DNA-based supercomputing,” Chinese Journal of Computers, vol.31, no.12, pp.2173–2181, 2008.
    [39]
    Zhou Xu, Zhou Yantao, Ouyang Aijia, et.al, “An efficient tile assembly model for maximum clique problem,” Journal of Computer Research and Development, vol.51, no.6, pp.1253–1262, 2014.
  • 加载中

Catalog

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

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

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

    Figures(11)

    Article Metrics

    Article views (158) PDF downloads(17) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return