Among, Common and Disjoint Constraints

Abstract : Among, Common and Disjoint are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We show how computational complexity can be used to determine whether achieving the highest level of consistency is tractable. For tractable constraints, we present a polynomial propagation algorithm and compare it to logical decompositions with respect to the amount of constraint propagation. For intractable cases, we show in many cases that a propagation algorithm can be adapted from a propagation algorithm of a similar tractable one.
Type de document :
Communication dans un congrès
Proceedings CSCLP: Revised Selected and Invited Papers, Uppsala, Sweden, pp.29-43, 2005, LNCS
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00378928
Contributeur : Isabelle Gouat <>
Soumis le : lundi 27 avril 2009 - 12:29:45
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

  • HAL Id : lirmm-00378928, version 1

Collections

Citation

Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. Among, Common and Disjoint Constraints. Proceedings CSCLP: Revised Selected and Invited Papers, Uppsala, Sweden, pp.29-43, 2005, LNCS. 〈lirmm-00378928〉

Partager

Métriques

Consultations de la notice

73