A major overhead of both maxRPC2 and maxRPCrm is the following. When searching for a PC-witness for a pair of values (ai, aj ) in a third variable xk, they always start the search from scratch, i.e. from the first available value in D(xk).

As these searches can be repeated many times during search, there can be many redundant constraint checks. In contrast, maxRPC1 manages to avoid searching from scratch through the use of an additional data structure. This saves many constraint checks, albeit resulting in O(end) space complexity and requiring costly maintainance of this data structure during search. The algorithms we describe below largely eliminate these redundant constraint checks with lower space complexity, and in the case of maxRPC3rm with only light use of data structures.

## 3 New Algorithms For Maxrpc

We first recall the basic ideas of algorithms maxRPC2 and maxRPCrm as described in [7] and [10]. Both algorithms use a propagation list L where variables whose domain is pruned are added. Once a variable xj is removed from L all neighboring variables are revised to delete any values that are no longer maxRPC. For any value ai of such a variable xithere are two possible reasons for deletion. The first, which we call *PC-support loss* hereafter, is when the unique PC-support aj ∈ D(xj ) for ai has been deleted. The second, which we call *PC-witness loss* hereafter, is when the unique PC-witness aj ∈ D(xj ) for the pair (ai, ak), where ak is the unique PC-support for ai on some variable xk, has been deleted. In both cases value aiis no longer maxRPC.

We now give a unified description of algorithms maxRPC3 and maxRPC3rm.

Both algorithms utilize data structures **LastP C** and **LastAC** which have the following functionalities: For each constraint cij and each value ai ∈ D(xi),
LastP Cxi,ai,xjand **LastAC**xi,ai,xj give (point to) the most recently discovered PC and AC supports of aiin D(xj )respectively. Initially, all **LastP C** and **LastAC**
pointers are set to a special value NIL, considered to precede all values in any domain. Algorithm maxRPC3 updates the **LastP C** and **LastAC** structures incrementally like maxRPC2 and AC2001/3.1 respectively do. In contrast, algorithm maxRPC3rm uses these structures as residues like maxRPCrm and ACrm do.

The pseudocode for the unified description of maxRPC3 and maxRPC3rm is given in Algorithm 1 and Functions 2, 3, 4. We assume the existence of a global Boolean variable RM which determines whether the algorithm presented is instantiated to maxRPC3 or to maxRPC3rm. If RM is true, the algorithm used is maxRPC3rm. Otherwise, the algorithm is maxRPC3.

Being coarse-grained, Algorithm 1 uses a propagation list L where variables that have their domain filtered are inserted. If the algorithm is used for preprocess-