A Correct Path Consistency Algorithm and An Optimal Generalized Arc Consistency Algorithm

Abstract : This paper presents a careful construction of a correct version of the path consistency algorithm published in (Moh-86). The same kind of construction is then used to extend the optimal arc consistency algorithm AC4 into GAC4 for n-ary constraints. Furthermore an evaluation technic is provided which evaluates the algorithm on the basis of the size of the constraints. It is proven that both AC4 and its extension are linear in the size of the constraints and therefore are optimal.
Type de document :
Rapport
[Research Report] 87-R-030, 1987
Liste complète des métadonnées

https://hal.inria.fr/inria-00548481
Contributeur : Thoth Team <>
Soumis le : lundi 20 décembre 2010 - 08:49:36
Dernière modification le : jeudi 11 janvier 2018 - 06:23:18

Identifiants

  • HAL Id : inria-00548481, version 1

Collections

Citation

Roger Mohr. A Correct Path Consistency Algorithm and An Optimal Generalized Arc Consistency Algorithm. [Research Report] 87-R-030, 1987. 〈inria-00548481〉

Partager

Métriques

Consultations de la notice

42