Skip to Main content Skip to Navigation
Conference papers

Filtrage pour l'isomorphisme de sous-graphe

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:38:59 PM
Last modification on : Friday, October 1, 2021 - 9:54:07 AM
Long-term archiving on: : Friday, September 21, 2012 - 4:05:56 PM


Files produced by the author(s)


  • HAL Id : inria-00151229, version 1


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⟩



Record views


Files downloads