The Parallel Computing of a Subgraph Isomorphism Algorithm
Given two graphs G1 and G2, the goal of subgraph isomorphism problem is to find a subgraph of G2 isomorphic to G1. This problem is known to be NP-complete. An effective way to cope with the problem is backtracking which can avoid visiting all the states by applying some heuristic rules and necessary conditions. An asynchronous computing strategy of the problem and its implementation on a Tianchao Dawning 3000 are discussed. The main idea of the parallel algorithm is that the whole backtracking procedure is decomposed into many parts. Each part only needs to finish its own backtracking procedure. Experimental results show that the parallel algorithm gives high speedup and efficiency.
并行计算 程序设计 算法效率
Yu Ensheng Wang Xicheng
Department of Computer Science and Engineering,Dalian University of Technology,Dalian 116023,China Department of Engineering Mechanics,Dalian University of Technology,Dalian 116023,China;State Key La
国内会议
辽宁大连
英文
76-79
2004-07-26（万方平台首次上网日期，不代表论文的发表时间）