作者
Claude-Guy Quimper, Alejandro López-Ortiz, Peter Van Beek, Alexander Golynski
发表日期
2004
研讨会论文
Principles and Practice of Constraint Programming–CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27-October 1, 2004. Proceedings 10
页码范围
542-556
出版商
Springer Berlin Heidelberg
简介
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.
引用总数
学术搜索中的文章
CG Quimper, A López-Ortiz, P Van Beek, A Golynski - Principles and Practice of Constraint Programming–CP …, 2004