(PDF) Claude-Guy Quimper, Alejandro Lopez-Ortiz, Peter van Beek, and Alexander Golynski. Improved algorithms for the global cardinality constraint. Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, Toronto, Ontario, 542-556, September, 2004.
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^2d + 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.