Improved Algorithms for the Global Cardinality Constraint, Claude-Guy Quimper, A. López-Ortiz, Peter van Beek, and Alexander Golynski. In Proceedings of 10^th International Conference on Principles and Practice of Constraint Programming (CP), Lecture Notes in Computer Science, 3258, Springer, 2004. [Postscript file]

Abstract.
We study the global cardinality constraint (gcc) and propose an O(n^(3/2) 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 the global cardinality constraint is universal in constant time and prove that it is NP-Hard to maintain domain consistency on extended-GCC.