# Alan K. Mackworth's Publications

•
Sorted by Date •
Classified by Publication Type •
Sorted by First Author Last Name •
Classified by Author Last Name •

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

Alan K. Mackworth and E. C. Freuder. The Complexity of Some Polynomial Network Consistency
Algorithms for Constraint Satisfaction Problems. *Artificial Intelligence*, 25(1):65–74, 1985. This
paper was honoured in *Artificial Intelligence* 59, 1-2, 1993
as one of the thirty most cited papers in the history of *Artificial Intelligence*.

### Download

[PDF]1.0MB

### 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.

### BibTeX

@Article{AI85,
author = {Alan K. Mackworth and E. C. Freuder},
title = {The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems},
year = {1985},
journal = {Artificial Intelligence},
volume = {25},
number = {1},
pages = {65--74},
note = {<font color="red">This paper was honoured in <I>Artificial Intelligence</I> 59, 1-2, 1993
as one of the thirty most cited papers in the history of <I>Artificial Intelligence</I>. </font>},
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.},
bib2html_pubtype ={Refereed Journal},
bib2html_rescat ={},
}

Generated by
bib2html.pl
(written by Patrick Riley
) on
Wed Apr 23, 2014 19:08:34