A performance study on deterministic label graph matching algorithm

Graph matching is a fundamental mechanism of many applications including computer visioning, knowledge reasoning and network analysis. This paper experimented two deterministic graph matching algorithm (VF2 algorithm and GE algorithm) and made a performance comparison between them. After analyzing the natures and characters of deterministic graph matching algorithms, this paper proposed a new performance metric system of time complexity with number of visited state and times of label checking. And a new measuring system was designed by independently creating test sample graphs of pattern and target. The experiment revealed some built-in problems of the VF2 algorithm. And a GE algorithm was acknowledged of good performance. This work also provided good hits for further improvement of graph matching.