Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Bound Consistency for Binary Length-Lex Set Constraints

Abstract : The length-lex representation has been recently proposed for representing sets in Constraint Satisfaction Problems. The length-lex representation directly captures cardinality information , provides a total ordering for sets, and allows bound consistency on unary constraints to be enforced in time˜Otime˜ time˜O(c), where c is the cardinality of the set. However, no algorithms were given to enforce bound consistency on binary constraints. This paper addresses this open issue. It presents algorithms to enforce bound consistency on disjointness and cardinality constraints in time O(c 3). Moreover, it presents a generic bound-consistency algorithm for any binary constraint S which requires˜Orequires˜ requires˜O(c 2) calls to a feasibility subrou-tine for S.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.umontpellier.fr/hal-01742388
Contributeur : Carmen Gervet <>
Soumis le : samedi 24 mars 2018 - 17:13:18
Dernière modification le : mardi 14 janvier 2020 - 10:38:15
Archivage à long terme le : : jeudi 13 septembre 2018 - 04:24:10

Fichier

aaai08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01742388, version 1

Citation

Pascal van Hentenryck, Justin Yip, Carmen Gervet, Grégoire Dooms. Bound Consistency for Binary Length-Lex Set Constraints. AAAI, 2008, Chicago, United States. ⟨hal-01742388⟩

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

25