Probe Machine Based Computing Model for Maximum Clique Problem
Probe Machine Based Computing Model for Maximum Clique Problem作者机构：Department of Computer Huainan Union University School of Electronic and Information Engineering Anhui University of Science & Technology School of Mathematics Physics and Statistics Shanghai University of Engineering Science School of Mathematics and Big Data Anhui University of Science & Technology
出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))
年 卷 期：2022年第31卷第2期
页 面：304-312页
核心收录：
学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金：supported by the National Natural Science Foundation ty (KJ2019A0538) of China (62072296,61702008) Natural Science Foundation of Anhui University (KJ2019A0538)
主 题：maximal cliques maximum clique problem searching capacity data library NP-complete problem computational complexity model lie induced subgraph probe operation undirected graph mathematic model graph theory parallel algorithms optimisation parallelism computing model vertex probe library probe machine
摘 要：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 *** the other hand, the proposed model is highly *** work demonstrates that PM is superior to TM in terms of searching capacity when tackling NP-complete problem.
同方期刊数据库