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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
https://hal.inria.fr/inria-00085796
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 11:46:41 AM
Last modification on : Friday, June 22, 2018 - 9:32:42 AM
Long-term archiving on : Tuesday, April 6, 2010 - 12:09:14 AM

File

28.pdf

Identifiers

  • HAL Id : inria-00085796, version 1

Collections

JFPC06 | UNIV-NANTES | LINA | LINA-TASC | INFO | IMT-ATLANTIQUE

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. ⟨inria-00085796⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

607

Files downloads

141

Contact


archive-ouverte@inria.fr