Skip to Main content Skip to Navigation
Journal articles

Arc-Consistency and Arc-Consistency Again

Christian Bessière 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : There is no need to show the importance of arc-consistency in Constraint Networks. Mohr and Henderson [9] have proposed AC-4, an algorithm with optimal worst-case time complexity. But it has two drawbacks: its space complexity and average time complexity. In problems with many solutions, where constraints are large, these drawbacks become so important that users often replace AC-4 by AC-3 [8], a non-optimal algorithm. In this paper, we propose a new algorithm, AC-6, which keeps the optimal worst-case time complexity of AC-4 while working out the drawback of space complexity. Moreover, the average time complexity of AC-6 is optimal for constraint networks where nothing is known about the constraint semantics.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02310614
Contributor : Isabelle Gouat <>
Submitted on : Thursday, October 10, 2019 - 12:24:19 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

File

aij94.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Christian Bessière. Arc-Consistency and Arc-Consistency Again. Artificial Intelligence, Elsevier, 1994, 65 (1), pp.179-190. ⟨10.1016/0004-3702(94)90041-8⟩. ⟨lirmm-02310614⟩

Share

Metrics

Record views

62

Files downloads

118