- Origin
Derived from and .
- Constraint
-
- Synonym
.
- Arguments
| |
| |
| |
| |
- Restrictions
|
|
|
|
|
|
|
|
|
|
- Purpose
is less than or equal
to the number of variables
that are assigned value .
is greater than or equal
to the number of variables
that are assigned value .
The number of assignments of the form
() is greater than or equal to
and less than or equal to .
- Example
-
The constraint holds since:
Values 1, 5 and 6 are respectively assigned to the set of variables
(i.e.,Β ),
(i.e.,Β ) and
(i.e.,Β ).
Note that, due to the definition of the constraint,
the fact that is assigned to 1 is not counted.
In addition the number of assignments of the form
() is greater than or equal to
and less than or equal to .
- Typical
|
|
|
|
|
|
|
- Symmetries
Items of are permutable.
can be decreased to any value .
can be increased to any value .
- Usage
Within the context of the constraint
the constraint allows to model
a minimum and maximum degree constraint on each vertex of our trees.
- Algorithm
The flow algorithm that handles the original
constraintΒ [Regin96] can be adapted to the context of the
constraint. This is done by creating
an extra value node representing the loops corresponding to the roots of
the trees.
- See also
generalisation:
Β ( replaced by ).
implied by:
.
related:
Β (graph partitioning by a set of trees with degree restrictions).
root concept:
Β (assignment of a to its position is ignored).
- Keywords
constraint type:
value constraint.
filtering:
flow.
For all items of :
