Graph matching arises in many domains from the comparison of biological networks to scene recognition problems. Efficient methods are available for exact matching and people are now interested in approximate graph matching. Given an input query graph, the objective is to find this query in a target graph, allowing some approximations : node gaps, structural differences,…