Filtrage pour l'isomorphisme de sous-graphe

Résumé : On introduit ici un algorithme de filtrage dédié au problème de l'isomorphisme de sous-graphe consistant à décider s'il existe une copie d'un graphe motif dans un graphe cible. L'idée principale est d'étiqueter chaque sommet en fonction de ses relations avec les autres sommets du graphe. Cet étiquetage peut être renforcé en ajoutant des informations sur les étiquettes des sommets voisins de chaque sommet. Un tel renforcement peut être effectué itérativement jusqu'à l'obtention d'un point fixe. On définit un ordre partiel sur les étiquettes afin d'exprimer leur compatibilité pour l'isomorphisme de sous-graphe. Cet ordre partiel est utilisé pour filtrer les domaines. Les résultats expérimentaux montrent que ce filtrage permet de résoudre plus efficacement le problème de l'isomorphisme de sous-graphe que des approches dédiées, pour des instances ``scale free''.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, France. 2007, JFPC07
Liste complète des métadonnées

https://hal.inria.fr/inria-00151229
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:38:59
Dernière modification le : jeudi 19 avril 2018 - 14:38:03
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:05:56

Fichier

19.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151229, version 1

Citation

Stéphane Zampelli, Yves Deville, Christine Solnon, Sébastien Sorlin, Pierre Dupont. Filtrage pour l'isomorphisme de sous-graphe. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, France. 2007, JFPC07. 〈inria-00151229〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

170