A Correct Path Consistency Algorithm and An Optimal Generalized Arc Consistency Algorithm
Résumé
This paper presents a careful construction of a correct version of the path consistency algorithm published in (Moh-86). The same kind of construction is then used to extend the optimal arc consistency algorithm AC4 into GAC4 for n-ary constraints. Furthermore an evaluation technic is provided which evaluates the algorithm on the basis of the size of the constraints. It is proven that both AC4 and its extension are linear in the size of the constraints and therefore are optimal.