AC-5*:An Improved AC-5 and its Specializations

Simple item page
dc.contributor.authorBing LIUen_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T07:00:17Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T07:00:17Z
dc.date.issued1996-04-01T00:00:00Zen_US
dc.description.abstractMany general and specific arc consistency algorithms have been produced in the past for solving Constraint Satisfaction Problems (CSP). The important general algorithms are AC-3, AC-4, AC-5 and AC-6. AC-5 is also a generic algorithm. It can be reduced to AC-3, AC-4 and AC-6. Specific algorithms are efficient specializations of the general ones for specific constraints. Functional, anti-functional and monotonic constraints are three important classes of specific constraints. AC-5 has been specialized to produce an O(ed) algorithm (in time) for these classes of constraints. However, this specialization does not reduce the space requirement. In practical applications, both time and space requirements are important criteria in choosing an algorithm. This paper makes two contributions. First, we propose an improved generic arc consistency algorithm, called AC-5*. It can be specialized to reduce both time and space complexities. Second, we present a more efficient technique for handling an important subclass of functional constraints, namely increasing functional constraints. This technique is significant because in practice almost all functional constraints are actually increasing functional constraints.en_US
dc.format.extent90552 bytesen_US
dc.format.extent698721 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1342en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRC4/96en_US
dc.titleAC-5*:An Improved AC-5 and its Specializationsen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
682.34 KB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
88.43 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports