Filtrage basé sur des propriétés de graphe

Cet article presente un schema de filtrage generique, base sur la description de contraintes globales sous la forme de proprietes de graphes. Cette description est definie par un reseau de contraintes binaires et une liste de proprietes de graphe elementaires : chaque solution de la contrainte globale correspond a un sous-graphe du reseau initial, dans lequel ne sont retenues que les contraintes binaires satisfaites. Ce sous-graphe doit verifier les proprietes de graphe qui definissent la contrainte. Le filtrage consiste en l'identification des arcs du reseau qui appartiennent ou non aux sous-graphes solution. L'objectif est de construire, a cote du catalogue de contraintes, une liste de regles de filtrage systematiques. Ces regles sont basees sur un ensemble limite de proprietes. Elles s'appliquent a toutes les contraintes du catalogue decrites a l'aide de ces proprietes. Nous illustrons ce principe sur les proprietes de graphe les plus usuelles, et nous experimentons notre technique sur la contrainte group.