Performance evaluation of the VF graph matching algorithm

The paper discusses the performance of a graph matching algorithm tailored for dealing with large graphs in computer vision without using information about the topology of the graphs to be matched. The algorithm, presented in more detail in other papers (and publicly available on the WWW as VF), is now discussed with reference to its computational complexity and memory requirements. The performance analysis is carried out by theoretically characterizing the matching time and the required memory in the best and worst cases. The theoretical analysis is completed by tests on a database of graphs randomly generated. The algorithm is compared with the one proposed by Ullmann (1976): experimental results confirmed the theoretical expectations, highlighting the overall efficiency of the algorithm. Some results obtained by researchers who recently used the algorithm in application domains requiring a massive use of graph matching techniques are finally reported.