) time, where e is the number of constraint arcs,
and l is the domain size [Mohr & Henderson, 1986].
AC-4 builds and maintains several data structures, described in
Figure 16, to allow it to efficiently achieve arc
consistency in a CSP. Note that we have modified the notation
slightly to eliminate subscripts (which become quite cumbersome for
the path consistency algorithm). Figure 17 shows
the code for initializing the data structures, and Figure
18 contains the algorithm for eliminating
inconsistent labels from the domains. This algorithm requires
) time, where e is the number of constraint arcs,
and l is the domain size [Mohr & Henderson, 1986].
Figure 16: Data structures and notation for the arc consistency algorithm, AC-4.
In AC-4, if the label 
is compatible with 
, then a supports b (and vice versa). To keep track
of how much support each label a has, the number of labels in
which are compatible with a in 
are counted and the
total stored in Counter[(i,j), a] by the algorithm in Figure
17. If any Counter[(i,j), a] is zero, then a is
removed from (because it cannot appear in any solution), the
ordered pair (i,a) is placed on the List, and M[i,a] is set to 1 (to
avoid removing the element a from more than once). The
algorithm must also keep track of which labels that label a supports
by using S[i, a], a set of arc and label pairs. For example, S 
means that a in supports b and
c in . If a is ever removed from , then b and c
will loose some of their support.
After the preprocessing step in Figure 17, the
algorithm in Figure 18 loops until List becomes
empty, at which point the CSP is arc consistent. When (i,a) is
popped off List by this procedure, for each element (j,b) in
S[i,a], Counter[(j,i), b] is decremented. If Counter[(j,i), b]
becomes zero, b would be removed from , (j,b) placed on
List, and M[j,b] set to 1.
Figure 17: Initialization of the data structures for AC-4.
Figure 18: Eliminating inconsistent labels from the domains in AC-4.
Next, we describe the MUSE arc consistency algorithm for a MUSE CSP, called MUSE AC-1. We purposely keep our notation and presentation of MUSE AC-1 as close as possible to that of AC-4 so that the reader can benefit from the similarity of the two algorithms.