Arc consistency algorithms are widely used to prune the search space
of Constraint Satisfaction Problems (CSPs). Coarse-grained arc
consistency algorithms like AC-3 and AC-2001 are efficient in
establishing arc consistency on a given CSPs. These algorithms
repeatedly carry out revisions. Revisions require support checks for
identifying and deleting all unsupported values from the domains. For
difficult problems, many values find some support while revising
domains. Indeed, many revisions are ineffective, that is they cannot
delete any value and consume a lot of checks and time. We propose two
solutions to overcome these problems. First we introduce the notion of
a Support Condition (SC). If the SC holds then it guarantees that a
given value has some support. SCs reduce support checks while
maintaining arc consistency during search. Second, we introduce the
notion of a Revision Condition (RC). If the RC holds then it
guarantees that all values of a given domain have some support. An RC
avoids a candidate revision and queue maintenance overhead. Our
experimental results show that for random problems, SCs reduce the
support checks equired by MAC-3 (MAC-2001) up to 90% (72%). The RCs
avoid at least 50% of the total revisions. Combining the two, results
in reducing 50% of the solution time.