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

https://hal.inria.fr/inria-00548487
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

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

180