A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints
Thierry Petit, Nicolas Beldiceanu and Xavier Lorca
This paper introduces the SEQ_BIN meta-constraint with a polytime algorithm achieving generalized arc-consistency. SEQBIN can be used for encoding counting constraints such as CHANGE, SMOOTH, or INCREASING_NVALUE. For all of them the time and space complexity is linear in the sum of domain sizes, which improves or equals the best known results of the literature.