Experimental Study On Extended Subgraph Isomorphism Problem

Subgraph isomorphism problem is important in graph theory. From the mathematical point of view, NPC problems are a challenge to theoretical computer sceience. Also, the problem has a wide range of applications, including pattern recognition and computer vision, bioinformatics, computer-aided design and etc.The traditional subgraph isomorphism problem can be defined as follow: given two graphs, we want to know whether one graph is isomorphic to a subgraph of the other graph. In graph database, this is a fundamental problem to do search operation. In fact, we can enhance the flexibility of search operation by not only allowing the user to input a substructure, but to add weights to each edge, which indicate the distance constraint between the two adjacent vertices. If there exists a injection that the distances between every two nodes are no greater than the corresponding constraints, the system can return the graph as a matching one. We call this new problem extended subgraph isomorphism problem.In this paper, we propose improved algorithms to solve extended subgraph isomorphism problem, that is to optimize the adding-edge procedure to deal with the distance information, according to the different characteristics of Ullmann and QuickSI. In the formal one, shortest distances for every node to each label in query are computed to cut branches, and in the latter one, we use the dynamic BFS procedure to reduce the running time for adding edges. The experiments results are achieved using AIDS database, and give the comparison of under different edge weight settings.