%0 Journal Article
%T Optimized Backtracking for Subgraph Isomorphism
%A Lixin Fu
%A Shruthi Chandra
%J International Journal of Database Management Systems
%D 2013
%I Academy & Industry Research Collaboration Center (AIRCC)
%X Subgraph isomorphism is a fundamental graph problem with many important applications. Given twographs G and SG, the subgraph isomorphism problem is to determine whether G contains a subgraph thatis isomorphic to SG. It is well known that the problem is NP complete in the worst case. In this paper, wepresent two new algorithms for subgraph isomorphism problem for labeled graphs. If the graphs haveunique vertex labels, we designed a new algorithm based on modified adjacency list that has achievedlinear performance. For general graphs we present another algorithm using optimized backtrackingsearch. Though this algorithm doesnĄ¯t guarantee polynomial time, it reduces the search space by applyingseveral pruning techniques. Simulation results show that our new algorithms are competitive with classicUllmanĄ¯s algorithm and more recent VF2.
%K Subgraph isomorphism
%K backtracking
%K algorithm
%K graph matching
%U http://airccse.org/journal/ijdms/papers/4612ijdms01.pdf