Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.artint.2005.02.004
DC FieldValue
dc.titleAn optimal coarse-grained arc consistency algorithm
dc.contributor.authorBessière, C.
dc.contributor.authorRégin, J.-C.
dc.contributor.authorYap, R.H.C.
dc.contributor.authorZhang, Y.
dc.date.accessioned2013-07-04T07:38:24Z
dc.date.available2013-07-04T07:38:24Z
dc.date.issued2005
dc.identifier.citationBessière, C., Régin, J.-C., Yap, R.H.C., Zhang, Y. (2005). An optimal coarse-grained arc consistency algorithm. Artificial Intelligence 165 (2) : 165-185. ScholarBank@NUS Repository. https://doi.org/10.1016/j.artint.2005.02.004
dc.identifier.issn00043702
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39294
dc.description.abstractThe use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints. © 2005 Elsevier B.V. All rights reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.artint.2005.02.004
dc.sourceScopus
dc.subjectArc consistency
dc.subjectConstraint networks
dc.subjectConstraint programming systems
dc.subjectNon-binary constraints
dc.subjectPath consistency
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1016/j.artint.2005.02.004
dc.description.sourcetitleArtificial Intelligence
dc.description.volume165
dc.description.issue2
dc.description.page165-185
dc.description.codenAINTB
dc.identifier.isiut000229853600002
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

145
checked on Nov 8, 2019

WEB OF SCIENCETM
Citations

95
checked on Oct 31, 2019

Page view(s)

77
checked on Oct 28, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.