Bound Consistency for Binary Length-Lex Set Constraints
Résumé
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.
Domaines
Intelligence artificielle [cs.AI]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...