5.211. k_used_by
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Type
- Argument
- Restrictions
- Purpose
Given sets of domain variables, the constraint forces a constraint between each pair of consecutive sets.
- Example
-
The constraint holds since:
The multiset of values associated with the second collection of variables is included into the multiset associated with the first collection of variables.
The multiset of values associated with the third collection of variables is included into the multiset associated with the second collection of variables.
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Arg. properties
Contractible wrt. .
- Remark
Similarly to the constraintΒ [ElbassioniKatrielKutzMahajan05], finding out whether the constraint has a solution or not is NP-hard when we have more than one constraint.
- See also
common keyword: , , Β (system of constraints).
- Keywords
characteristic of a constraint: sort based reformulation.
combinatorial object: multiset.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.211.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a constraint.
Figure 5.211.1. Initial and final graph of the constraint
(a) (b)