Abstract | ||
---|---|---|
The Same constraint takes two sets of variables X and Z such that |X|=|Z| and assigns values to them such that the multiset of values assigned to the variables in X is equal to the multiset of values assigned to the variables in Z. In this paper we extend the Same constraint in a GCC-like manner by adding cardinality requirements on the values. That is, for each value we have a lower and upper bound on the number of variables that can be assigned this value. We show an algorithm that achieves arc-consistency for this constraint and a faster algorithm that achieves bound-consistency for a restricted case of it. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/11402763_1 | CSCLP |
Keywords | Field | DocType |
restricted case,gcc-like manner,gcc-like restriction,cardinality requirement,faster algorithm,variables x,arc consistency | Combinatorics,Upper and lower bounds,Multiset,Constraint programming,Bipartite graph,Cardinality,Priority queue,Count data,Constraint logic programming,Mathematics | Conference |
Volume | ISSN | ISBN |
3419 | 0302-9743 | 3-540-25176-6 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nicolas Beldiceanu | 1 | 547 | 51.14 |
Irit Katriel | 2 | 176 | 13.72 |
Sven Thiel | 3 | 121 | 9.32 |