论文部分内容阅读
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.