Graphes et contraintes

Cette thèse propose une approche de filtrage originale, SND en abrégé pour Scoring-based Neighborhood Dominance, pour le problème d’isomorphisme de sous- graphe. En raisonnant sur des propriétés de dominance entre sommets basées sur diverses fonctions de score et de voisinage, SND apparait comme un puissant mécanisme de filtrage. Une spécialisation de SND est étudiée, elle est basée sur le nombre de chemins de longueur k comme fonction de score ainsi que trois manières de considérer le voisinage. Avec cette spécialisation, il est montré que SND est plus puissant que LAD et incomparable à SAC (Singleton Arc Consistency). L'étude expérimentale montre que SND atteint dans la plupart des cas les mêmes performances en terme de filtrage que SAC tout en étant plus rapide de plusieurs ordres de grandeurs. Cela permet de résoudre le problème d’isomorphisme de sous-graphe en étant beaucoup plus efficace que MAC et légèrement meilleur que LAD.Un solveur de contraintes est également proposé ainsi qu'une optimisation du processus de propagation de MAC.