Arc and Path Consistency Revisited

Abstract : Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in Image (a general constraint satisfaction system) and local consistency methods [3].
Type de document :
Article dans une revue
Artificial Intelligence, Elsevier, 1986, 28, pp.225--233. 〈10.1016/0004-3702(86)90083-4〉
Liste complète des métadonnées
Contributeur : Thoth Team <>
Soumis le : lundi 20 décembre 2010 - 08:49:39
Dernière modification le : jeudi 11 janvier 2018 - 06:23:18

Lien texte intégral




Roger Mohr, Thomas Henderson. Arc and Path Consistency Revisited. Artificial Intelligence, Elsevier, 1986, 28, pp.225--233. 〈10.1016/0004-3702(86)90083-4〉. 〈inria-00548487〉



Consultations de la notice