- a *wcon*: selects the arc (cij ,xi) such that cij has the highest weight *wcon* among all constraints appearing in an arc in Q.

- a *wdeg*: selects the arc (cij ,xi) such that xi has the highest weighted degree *wdeg* among all variables appearing in an arc in Q.

- a *dom/wdeg*: selects the arc (cij ,xi) such that xi has the smallest ratio between current domain size and weighted degree among all variables appearing in an arc in Q.

- a *dom/wcon*: selects the arc (cij ,xi) having the smallest ratio between the current domain size of xi and the weight of cij among all arcs in Q.
The call to one of the proposed arc-oriented heuristics can be attached to line 3 of Algorithm 1. Note that heuristics a *dom/wdeg* and a *dom/wcon* favor variables with small domain size hoping that the deletion of their few remaining values will lead to a DWO. To strictly follow the "ASAP principle" which calls for early value deletions we intend to evaluate the following heuristics in the future:

- a dom/wdeg *inverse*: selects the arc (cij ,xi) such that xj has the smallest ratio between current domain size and weighted degree among all variables appearing in an arc in Q.

- a dom/wcon *inverse*: selects the arc (cij ,xi) having the smallest ratio between the current domain size of xj and the weight of cij among all arcs in Q.
Heuristics a dom/wdeg *inverse* and a dom/wcon *inverse* favor revising arcs
(cij ,xi) such that xj , i.e. the other variable in constraint cij , has small domain size. This is because in such cases it is more likely that some values in D(xi) will not be supported in D(xj ), and hence will be deleted.

Variable-oriented heuristics are tailored for the variable-oriented variant of AC-3 where the list of revisions Q stores variables. For each of the heuristics given below we specify the variable that it selects. The names of the heuristics are preceded by an "v" to denote that they are tailored for variable-oriented propagation.

- v *wdeg*: selects the variable having the highest weighted degree *wdeg* among all variables in Q.

- v *dom/wdeg*: selects the variable having the smallest ratio between current domain size and *wdeg* among all variables in Q.

The call to one of the proposed variable-oriented heuristics can be attached to line 4 of Algorithm 3. After selecting a variable, the algorithm revises, in some order, the constraints in which the selected variable participates (line 5).

Our heuristics process these constraints in descending order according to their corresponding weight.