Technical Reports

The ICICS/CS Reading Room

UBC CS TR-82-06 Summary

The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems, August 1982 Alan K. Mackworth and E. C. Freuder

Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. In this paper we analyze the time complexity of several node, arc and path consistency algorithms. Arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In that computational vision application the constraint graph is planar and so the complexity is linear in the number of variables.

If you have any questions or comments regarding this page please send mail to