Please use this identifier to cite or link to this item:
Title: Arc consistency during search
Authors: Likitvivatanavong, C. 
Zhang, Y.
Shannon, S.
Bowen, J.
Freuder, E.C.
Issue Date: 2007
Source: Likitvivatanavong, C.,Zhang, Y.,Shannon, S.,Bowen, J.,Freuder, E.C. (2007). Arc consistency during search. IJCAI International Joint Conference on Artificial Intelligence : 137-142. ScholarBank@NUS Repository.
Abstract: Enforcing arc consistency (AC) during search has proven to be a very effective method in solving Constraint Satisfaction Problems and it has been widely-used in many Constraint Programming systems. Although much effort has been made to design efficient standalone AC algorithms, there is no systematic study on how to efficiently enforce AC during search, as far as we know. The significance of the latter is clear given the fact that AC will be enforced millions of times in solving hard problems. In this paper, we propose a framework for enforcing AC during search (ACS) and complexity measurements of ACS algorithms. Based on this framework, several ACS algorithms are designed to take advantage of the residual data left in the data structures by the previous invocation(s) of ACS. The algorithms vary in the worst-case time and space complexity and other complexity measurements. Empirical study shows that some of the new ACS algorithms perform better than the conventional implementation of AC algorithms in a search procedure.
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.

Page view(s)

checked on Mar 9, 2018

Google ScholarTM


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