Published August 2012
| Version v1
Conference paper
An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization
Contributors
Others:
- Theory, Algorithms and Systems for Constraints (TASC) ; Laboratoire d'Informatique de Nantes Atlantique (LINA) ; Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Département informatique - EMN ; Mines Nantes (Mines Nantes)-Inria Rennes – Bretagne Atlantique ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- SICS ; Swedish Institute of Computer Science [Stockholm] (SICS)
- Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP ; Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)
- Luc De Raedt and Christian Bessière and Didier Dubois and Patrick Doherty and Paolo Frasconi and Fredrik Heintz and Peter J. F. Lucas
Description
This paper gives an O(nlog n) bound-consistency filtering algorithm for the conjunction alldifferent(V0,V1,...,Vn−1)∧ f(V0)⌖f(V1)⌖...⌖f(Vn−1)≤ cst, (V0,V1,...,Vn−1,cst∊ +), where (,⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.archives-ouvertes.fr/hal-00754079
- URN
- urn:oai:HAL:hal-00754079v1