Comments on Mohr and Henderson's path consistency algorithm

摘要

Mohr and Henderson have presented new algorithms for arc and path consistency in [1]. Though the underlying ideas of their algorithms are correct, the path consistency algorithm PC-3 is in error. In this paper we point out the errors in this algorithm and give a correct one. The time complexity and space complexity of the revised algorithm are also analyzed.