### Citation

(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.

### 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^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.

**Return to Publications**