Subgraph isomorphism is a fundamental graph problem with many important applications. Given two graphs G and SG, the subgraph isomorphism problem is to determine whether G contains a subgraph that is isomorphic to SG. It is well known that the problem is NP complete in the worst case. In this paper, we present two new algorithms for subgraph isomorphism problem for labeled graphs. If the graphs have unique vertex labels, we designed a new algorithm based on modified adjacency list that has achieved linear performance. For general graphs we present another algorithm using optimized backtracking search. Though this algorithm doesn’t guarantee polynomial time, it reduces the search space by applying several pruning techniques. Simulation results show that our new algorithms are competitive with classic Ullman’s algorithm and more recent VF2.
展开▼
