  Enforcing local consistencies is one of the main features of constraint
reasoning. Which level of local consistency should be used when searching for
solutions in a constraint network is a basic question. Arc consistency and
partial forms of arc consistency have been widely studied, and have been known
for sometime through the forward checking or the MAC search algorithms. Until
recently, stronger forms of local consistency remained limited to those that
change the structure of the constraint graph, and thus, could not be used in
practice, especially on large networks. This paper focuses on the local
consistencies that are stronger than arc consistency, without changing the
structure of the network, i.e., only removing inconsistent values from the
domains. In the last five years, several such local consistencies have been
proposed by us or by others. We make an overview of all of them, and highlight
some relations between them. We compare them both theoretically and
experimentally, considering their pruning efficiency and the time required to
enforce them.
