Performance evaluation of the VF graph matching algorithm
- 1 January 1999
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1172-1177
- https://doi.org/10.1109/iciap.1999.797762
Abstract
The paper discusses the performance of a graph matching algorithm tailored for dealing with large graphs without using information about the topology of the graphs to be matched. The algorithm, presented in more details in other papers (and publicly available on the WEB 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 J.R. Ullmann: 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.Keywords
This publication has 4 references indexed in Scilit:
- Subgraph Transformations for the Inexact Matching of Attributed Relational GraphsPublished by Springer Nature ,1998
- Structural Descriptions and Inexact MatchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- An Algorithm for Subgraph IsomorphismJournal of the ACM, 1976
- An Efficient Algorithm for Graph IsomorphismJournal of the ACM, 1970