de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Complete Bound Consistency for the Global Cardinality Constraint

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44744

Katriel,  Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45615

Thiel,  Sven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Katriel, I., & Thiel, S. (2005). Complete Bound Consistency for the Global Cardinality Constraint. Constraints, 10, 191-217.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2616-C
##### Abstract
We show an algorithm for bound consistency of {\em 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.