Improved Algorithms for the Global Cardinality Constraint
[.ps]
[.pdf]
Abstract
We study the global cardinality constraint (gcc) and propose an
O(n
1.5d) 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.
Bibtex Entry
