Nowadays, many real problems can be modeled as constraint satisfaction problems. Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction. In this paper we present a new algorithm, called 2-C3OP, that achieves 2-consistency in binary and non-normalized CSPs. This algorithm is a reformulation of 2-C3 algorithm and it performs the constraint checks bidirectionally using inference. The evaluation section shows that 2-C3OP achieve 2-consistency like 2-C3 and it is 40% faster. Furthermore, 2-C3OP performs less number of constraint checks than both AC3 and 2-C3.
['Marlene Arangú', 'Miguel A. Salido', 'Federico Barber']
2-C3OP: An Improved Version of 2-Consistency