- 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.
The rightmost part of FigureΒ 3.7.29
illustrates the corresponding flow model for the constraint
where there is a one-to-one correspondence between feasible flows in the flow model
and solutions of the constraint.
- 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 :
