Path consistency revisited
Manjeet Singh · 2002
One of the main factors limiting the use of path consistency algorithms in real life applications is their high space complexity. C. Han and C. Lee (1988) presented a path consistency algorithm, PC-4, with O(n/sup 3/a/sup 3/) space complexity, which makes it practicable only for small problems. The author presents a new path consistency algorithm, PC-5, which has an O(n/sup 3/a/sup 2/) space complexity while retaining the worst case time complexity of PC-4. Moreover, the new algorithm exhibits a much better average case time complexity. The new algorithm is based on the idea (due to C. Bessiere (1994)) that, at any time, only a minimal amount of support has to be found and recorded for a labeling to establish its viability; one has to look for at new support only if the current support is eliminated. The author also shows that PC-5 can be improved further to yield an algorithm, PC5++, with even better average case performance and the same space complexity.