Complete bound consistency for the global cardinality constraint

作     者：Katriel, I Thiel, S 

作者机构：Max Planck Inst Informat Saarbrucken Germany 

出 版 物：《CONSTRAINTS》 (约束)

年 卷 期：2005年第10卷第3期

页      面：191-217页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：EU IST Programme, (IST-1999-14186) Deutsche Forschungsgemeinschaft, DFG, (SA 933/1-1) 

主　　题：arc consistency bound consistency constraint propagation filtering algorithms flow global cardinality constraint global constraints graph algorithms matching 

摘      要：We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n ) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.