Optimized Algorithm of Extended Subgraph Isomorphism Problem
XU Kai-xuan, Rudolf Fleischer · Jisuanji gongcheng · 2011
This paper proposes an improved algorithm 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,it uses the dynamic BFS procedure to reduce the running time for adding edges.To give the comparison under different edge weight settings,it conducts series of experiments on AIDS database.Results suggest that the average performance of QuickSI algorithm is more than an order of magnitude faster.