A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

摘要

This paper introduces the seq.bin meta-constraint with a polytime algorithm achieving generalized arc-consistency. seq.bin 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.