Filtrage basé sur des contraintes tous différents pour l'isomorphisme de sous-graphe - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

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

Abstract

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.
Fichier principal
Vignette du fichier
solnon.pdf (185.68 Ko) Télécharger le fichier
Origin : Explicit agreement for this submission
Loading...

Dates and versions

inria-00519102 , version 1 (18-09-2010)

Identifiers

  • HAL Id : inria-00519102 , version 1

Cite

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⟩
58 View
85 Download

Share

Gmail Facebook Twitter LinkedIn More