Please use this identifier to cite or link to this item: https://doi.org/10.3233/978-1-61499-098-7-510
Title: A path-optimal GAC algorithm for table constraints
Authors: Lecoutre, C.
Likitvivatanavong, C. 
Yap, R.H.C. 
Issue Date: 2012
Citation: Lecoutre, C., Likitvivatanavong, C., Yap, R.H.C. (2012). A path-optimal GAC algorithm for table constraints. Frontiers in Artificial Intelligence and Applications 242 : 510-515. ScholarBank@NUS Repository. https://doi.org/10.3233/978-1-61499-098-7-510
Abstract: Filtering by Generalized Arc Consistency (GAC) is a fundamental technique in Constraint Programming. Recent advances in GAC algorithms for extensional constraints rely on direct manipulation of tables during search. Simple Tabular Reduction (STR), which systematically removes invalid tuples from tables, has been shown to be a simple yet efficient approach. STR2, a refinement of STR, is considered to be among the best filtering algorithms for positive table constraints. In this paper, we introduce a new GAC algorithm called STR3 that is specifically designed to enforce GAC during search. STR3 can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. Our experiments show that STR3 is much faster than STR2 when the average size of the tables is not reduced drastically during search. © 2012 The Author(s).
Source Title: Frontiers in Artificial Intelligence and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/77972
ISBN: 9781614990970
ISSN: 09226389
DOI: 10.3233/978-1-61499-098-7-510
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

22
checked on Jul 14, 2018

WEB OF SCIENCETM
Citations

1
checked on Jun 19, 2018

Page view(s)

31
checked on Jul 6, 2018

Google ScholarTM

Check

Altmetric


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