Making AC-3 an optimal algorithm

Yuanlin Zhang, Roland H.C. Yap

Research output: Contribution to journalConference articlepeer-review

63 Scopus citations

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.

Original languageEnglish
Pages (from-to)316-321
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2001
Event17th International Joint Conference on Artificial Intelligence, IJCAI 2001 - Seattle, WA, United States
Duration: Aug 4 2001Aug 10 2001

Fingerprint Dive into the research topics of 'Making AC-3 an optimal algorithm'. Together they form a unique fingerprint.

Cite this