Try variants of VF2 algorithm for subgraph isomorphism to test speed
- VF: C. Sansone L. P. Cordella, P. Foggia and M. Vento. Performance evaluation of the vf graph matching algorithm. Proc. of the 10th ICIAP, IEEE Computer Society Press, pp. 1172-1177, 1999.
- VF2: L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. Journal of the ACM (JACM) JACM Homepage archive Volume 23 Issue 1, Pages 31-42, 2004.
- VF2 Plus: Carletti V., Foggia P., Vento M. (2015) VF2 Plus: An Improved version of VF2 for Biological Graphs. In: Liu CL., Luo B., Kropatsch W., Cheng J. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2015. Lecture Notes in Computer Science, vol 9069. Springer, Cham
- VF3: Carletti V., Foggia P., Saggese A., Vento M. (2017) Introducing VF3: A New Algorithm for Subgraph Isomorphism. In: Foggia P., Liu CL., Vento M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2017. Lecture Notes in Computer Science, vol 10310. Springer, Cham
- branch and bound
- pruning
- best found, current + potential
- consider only connected subgraphs
- other graph properties, e.g., chromatic number is an upper bound for max clique size
- ordering
- VF2
- VF2+
- VF2++