Please use this identifier to cite or link to this item:
Title: Making AC-3 an optimal algorithm
Authors: Zhang, Y. 
Yap, R.H.C. 
Issue Date: 2001
Citation: Zhang, Y.,Yap, R.H.C. (2001). Making AC-3 an optimal algorithm. IJCAI International Joint Conference on Artificial Intelligence : 316-321. ScholarBank@NUS Repository.
Abstract: The AC-3 algorithm is a basic and widely used arc consistency enforcing algorithm in Constraint Satisfaction Problems (CSP). Its strength lies in that it is simple, empirically efficient and extensible. However its worst case time complexity was not considered optimal since the first complexity result for AC-3 [Mackworth and Freuder, 1985] with the bound O(ed3), where e is the number of constraints and d the size of the largest domain. In this paper, we show suprisingly that AC-3 achieves the optimal worst case time complexity with O(ed2). The result is applied to obtain a path consistency algorithm which has the same time and space complexity as the best known theoretical results. Our experimental results show that the new approach to AC-3 is comparable to the traditional AC-3 implementation for simpler problems where AC-3 is more efficient than other algorithms and significantly faster on hard instances.
Source Title: IJCAI International Joint Conference on Artificial Intelligence
ISSN: 10450823
Appears in Collections:Staff Publications

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

Google ScholarTM


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