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. / This thesis presents anoriginal filtering approach, called SND(Scoring- based Neighborhood Dominance), for the subgraph isomorphism problem. By reasoning on vertex dominance properties based on various scoring and neigh- borhood functions, SND appears to be a filtering mechanism of strong inference potential. For example, the recently proposed method LAD is a particular case of SND. A specialization is studied of SND : by considering the number of k-length paths in graphs and three ways of relating sets of vertices. With this specialization, we prove that SND is stronger than LAD and incomparable to SAC (Single- ton Arc Consistency). Our experimental results show that SND achieves most of the time the same filtering performances as SAC (while being several orders of magnitude faster), which allows one to find subisomorphism functions far more efficiently than MAC, while slightly outperforming LAD.
| Identifer | oai:union.ndltd.org:theses.fr/2017ARTO0402 |
| Date | 22 March 2017 |
| Creators | Samy Modeliar, Mouny |
| Contributors | Artois, Lecoutre, Christophe, Audemard, Gilles |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0016 seconds