## Abstract

We study the global cardinality constraint (gcc) and propose an O(n^{1.5}d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency where n is the number of variables, d the number of values in the domain, and c an output dependent variable smaller than or equal to n. We show how to prune the cardinality variables in O(n

^{2}d + n

^{2.66}) steps, detect if gcc is universal in constant time and prove that it is NP-Hard to maintain domain consistency on extended-GCC.