The complexity of some polynomial network consistency algorithms for constraint satisfaction problems
- 1 January 1985
- journal article
- Published by Elsevier BV in Artificial Intelligence
- Vol. 25 (1), 65-74
- https://doi.org/10.1016/0004-3702(85)90041-4
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. We analyze the time complexity of several node, arc and path consistency algorithms and prove that 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 the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables.Keywords
This publication has 6 references indexed in Scilit:
- On the Asymptotic Complexity of Matrix MultiplicationSIAM Journal on Computing, 1982
- A Sufficient Condition for Backtrack-Free SearchJournal of the ACM, 1982
- Increasing tree search efficiency for constraint satisfaction problemsArtificial Intelligence, 1980
- Synthesizing constraint expressionsCommunications of the ACM, 1978
- Consistency in networks of relationsArtificial Intelligence, 1977
- Networks of constraints: Fundamental properties and applications to picture processingInformation Sciences, 1974