Filtrage pour l'isomorphisme de sous-graphe - Archive ouverte HAL Access content directly
Conference Papers Year : 2007

Filtrage pour l'isomorphisme de sous-graphe

(1) , (2) , (3) , (3) , (2)
1
2
3
Yves Deville
  • Function : Author
  • PersonId : 840383
Pierre Dupont
  • Function : Author
  • PersonId : 840384

Abstract

A subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. We introduce in this paper a filtering algorithm dedicated to this problem. The main idea is to label every node with respect to its relationships with other nodes of the graph, and to define a partial order on these labels in order to express compatibility of labels for subgraph isomorphism. This partial order over labels is used to filter domains. Labelings can also be strengthened by adding information from the labels of the neighbors. Such a strengthening can be applied iteratively until a fixpoint is reached. Practical experiments illustrate that our new filtering approach is more effective than state-of-the-art dedicated algorithms for scale free networks.
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''.
Fichier principal
Vignette du fichier
19.pdf (203.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00151229 , version 1 (01-06-2007)

Identifiers

  • HAL Id : inria-00151229 , version 1

Cite

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. ⟨inria-00151229⟩
123 View
216 Download

Share

Gmail Facebook Twitter LinkedIn More