The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems

ID
TR-82-06
Authors
Alan K. Mackworth and E. C. Freuder
Publishing date
August 1982
Abstract
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.