The coarse-grained arc consistency algorithms maintain a list of elements that need to be revised. It is well known that the performance of such algorithms is affected by the way in which the revisions are performed. In this paper, we propose a new variable-oriented propagation scheme that splits the propagation procedure into two independent phases. We show how it reduces the number of revisions and list operations. In experiments, we apply different revision ordering heuristics to this new variable-oriented scheme and compare them with the most efficient existing propagation schemes. The results from various structured and random problems show that the proposed propagation scheme reduces the number of revisions and offers speed-ups.
展开▼
