Analyzing Subgraph Isomorphism on Graphs with Diverse Structural Properties
Noorul Amin, Kifayat Ullah Khan, Young-Koo Lee · 2015
Isomorphic subgraphs finding is important in many real world applications. Being NP-hard problem, various approaches have been proposed by varying indexing, candidate generation, early pruning of unpromising regions, and graph traversal. While, recent research additionally emphasis on taking into account order of query or data graph vertices and compressing to make it best fit for subgraph isomorphism. However, subgraph isomorphism has not been evaluated deeply by summarized graph. Subgraph isomorphism performance can be improved by using summarized graphs with exactness. For this purpose, we evaluate subgraph isomorphism performance on a single large graph by using backtracking algorithm. We extend Ullman algorithm for original and summarized graph. We evaluate subgraph isomorphism performance on both original and summarized version of graph through experiments on publically available real world graph.