Filtrage pour l'isomorphisme de sous-graphe
(2007) Journées Francophones de Programmation par Contraintes (JFPC′07) — Location: Rocquencourt, France, (4.June.2007)
Files
jfpc2007_iso.pdf
Open Access - Adobe PDF
- 226.47 KB
Details
- Authors
- Abstract
- On introduit ici un algorithme de filtrage d´edi´e au probl`eme de l’isomorphisme de sous-graphe consistant `a d´ecider s’il existe une copie d’un graphe motif dans un graphe cible. L’id´ee principale est d’´etiqueter chaque sommet en fonction de ses relations avec les autres sommets du graphe. Cet ´etiquetage peut ˆetre renforc´e en ajoutant des informations sur les ´etiquettes des sommets voisins de chaque sommet. Un tel renforcement peut ˆetre effectu´e it´erativement jusqu’`a l’obtention d’un point fixe. On d´efinit un ordre partiel sur les ´etiquettes afin d’exprimer leur compatibilit´e pour l’isomorphisme de sous-graphe. Cet ordre partiel est utilis´e pour filtrer les domaines. Les r´esultats exp´erimentaux montrent que ce filtrage permet de r´esoudre plus efficacement le probl`eme de l’isomorphisme de sous-graphe que des approches d´edi ´ees, pour des instances “scale free”.
- Affiliations
LIRIS, CNRS UMR University of Lyon
Citations
Zampelli, S., Deville, Y., Solnon, C., Sorlin, S., & Dupont, P. (2007). Filtrage pour l’isomorphisme de sous-graphe. Journées Francophones de Programmation par Contraintes (JFPC′07), Rocquencourt, France,. https://hdl.handle.net/2078.5/226071