A Fast Algorithm for the Bound Consistency of Alldiff Constraints

Jean-Francois Puget

Some n-ary constraints such as the alldiff constraints arise naturally in real life constraint satisfaction problems (CSP). General purpose filtering algorithms could be applied to such constraints. By taking the semantics of the constrain into account, it is possible to design more efficient filtering algorithms. When the domains of the variables are totally ordered (e.g. all values are integers), then filtering based on bound consistency may be very useful. We present in this paper a filtering algorithm for the alldiff constraint based on bound consistency whose running time complexity is very low. More precisely, for a constraint involving n varialbles, the time complexity of the algorithm is O(nlog(n)) which improves previously published results. The implementation of this algorithm is discussed, and we give some experimental results that probe its practical utility.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.