Paper Info
Title
A fast arc consistency algorithm for n-ary constraints
Abstract
The GAC-Scheme has become a popular general purpose algorithm for solving n-ary constraints, although it may scan an exponential number of supporting tuples. In this paper, we develop a major improvement of this scheme. When searching for a support, our new algorithm is able to skip over a number of tuples exponential in the arity of the constraint by exploiting knowledge about the current domains of the variables. We demonstrate the effectiveness of the method for large table constraints.
Year
Venue
Keywords
2005
AAAI
major improvement,popular general purpose algorithm,exponential number,large table constraint,tuples exponential,new algorithm,fast arc consistency algorithm,current domain,n-ary constraint,arc consistency
Field
DocType
ISBN
Local consistency,Mathematical optimization,Exponential function,Arity,General purpose,Computer science,Tuple,Algorithm
Conference
1-57735-236-x
Citations 
PageRank 
References 
28
1.45
6
Authors
2
Name
Order
Citations
PageRank
Olivier Lhomme138628.48
Jean-charles Régin2131296.59