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

Nicolas Beldiceanu 1 Matts Carlsson 2 Sophie Demassey 1 Thierry Petit 1
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 ISL-SICS - Intelligent Systems Laboratory
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

28.pdf

Identifiants

  • HAL Id : inria-00085796, version 1

Collections

JFPC06 | LINA | LINA-TASC | MINES-NANTES | INFO

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>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

268

Téléchargements du document

91

Contact


archive-ouverte@inria.fr