Filtrage basé sur des contraintes tous différents pour l'isomorphisme de sous-graphe

Résumé : Le problème de l'isomorphisme de sous-graphe consiste à rechercher une copie d'un graphe motif dans un graphe cible. Ce problème peut être résolu par une exploration exhaustive combinèe avec des techniques de filtrage visant à élaguer l'espace de recherche. Cet article introduit un nouvel algorithme de filtrage basé sur des contraintes tous différents conditionnelles. Nous montrons que ce filtrage est plus fort que les autres filtrages, dans le sens où il coupe plus de branches, et qu'il est également plus efficace, dans le sens où il permet de résoudre de nombreuses instances plus rapidement.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.247-256, 2010
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00519102
Contributeur : Christophe Lecoutre <>
Soumis le : samedi 18 septembre 2010 - 09:16:35
Dernière modification le : jeudi 19 avril 2018 - 14:38:02
Document(s) archivé(s) le : mardi 23 octobre 2012 - 16:20:39

Fichier

solnon.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00519102, version 1

Citation

Christine Solnon. Filtrage basé sur des contraintes tous différents pour l'isomorphisme de sous-graphe. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.247-256, 2010. 〈inria-00519102〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

105