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

Résumé : Cet article présente un schéma de filtrage générique, basé sur la description de contraintes globales sous la forme de propriétés de graphes. Cette description est définie par un réseau de contraintes binaires et une liste de propriétés de graphe élémentaires : chaque solution de la contrainte globale correspond à un sous-graphe du réseau initial, dans lequel ne sont retenues que les contraintes binaires satisfaites. Ce sous-graphe doit vérifier les propriétés de graphe qui définissent la contrainte. Le filtrage consiste en l'identification des arcs du réseau qui appartiennent ou non aux sous-graphes solution. L'objectif est de construire, à côté du catalogue de contraintes, une liste de règles de filtrage systématiques. Ces règles sont basées sur un ensemble limité de propriétés. Elles s'appliquent à toutes les contraintes du catalogue décrites à l'aide de ces propriétés. Nous illustrons ce principe sur les propriétés de graphe les plus usuelles, et nous expérimentons notre technique sur la contrainte group.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, France. 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085796
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 11:46:41
Dernière modification le : lundi 21 juillet 2008 - 10:31:32
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:14

Fichier

Identifiants

  • HAL Id : inria-00085796, version 1

Collections

Citation

Nicolas Beldiceanu, Matts Carlsson, Sophie Demassey, Thierry Petit. Filtrage basé sur des propriétés de graphe. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, France. 2006. <inria-00085796>

Partager

Métriques

Consultations de
la notice

228

Téléchargements du document

89