Méthodes exactes et inexactes pour mesurer la similarité de graphes en reconnaissance structurelle de formes.
Vincenzo Carletti · HAL (Le Centre pour la Communication Scientifique Directe) · 2016
Graphs are widely employed in many application fields, such as biology, chemistry, social networks,databases and so on. Graphs allow to describe a set of objects together with their relationships.Analysing these data often requires to measure the similarity between two graphs. Unfortunately,due to its combinatorial nature, this is a NP-Complete problem generally addressed using differentkind of heuristics.In this Thesis we have explored two approaches to compute the similarity between graphs. Theformer is based on the exact graph matching approach. We have designed, VF3, an algorithm aimedto search for pattern structures within graphs. While, the second approach is an inexact graphmatching method which aims to compute an efficient approximation of the Graph Edit Distance(GED) as a Quadratic Assignment Problem (QAP).