Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00519102
Contributor : Christophe Lecoutre <>
Submitted on : Saturday, September 18, 2010 - 9:16:35 AM
Last modification on : Wednesday, November 20, 2019 - 2:31:28 AM
Document(s) archivé(s) le : Tuesday, October 23, 2012 - 4:20:39 PM

File

solnon.pdf
Explicit agreement for this submission

Identifiers

  • 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. ⟨inria-00519102⟩

Share

Metrics

Record views

136

Files downloads

184