Search
 
loader loading subjects...
cover
An O(nlog n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization
Nicolas Beldiceanu, Mats Carlsson, Thierry Petit, Jean-Charles Régin
145 - 150
10.3233/978-1-61499-098-7-145
Frontiers in Artificial Intelligence and Applications
Volume 242: ECAI 2012
Abstract

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.

Download
Creative Commons License