• Sorted by Date • Classified by Publication Type • Sorted by First Author Last Name • Classified by Author Last Name •
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.
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.
@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