TY - GEN
T1 - Functional elimination and 0/1/All constraints
AU - Zhang, Yuanlin
AU - Yap, Roland H.C.
AU - Jaffar, Joxan
PY - 1999
Y1 - 1999
N2 - We present new complexity results on the class of 0/1/All constraints. The central idea involves functional elimination, a general method of elimination whose focus is on the subclass of functional constraints. One result is that for the subclass of 'All' constraints, strong n-consistency and minimality is achievable in O(en) time, where e, n are the number of constraints and variables. The main result is that we can solve 0/1/All constraints in O(e(d + n)) time, where d is the domain size. This is an improvement over known results, which are O(ed(d + n)). Furthermore, our algorithm also achieves strong n-consistency and minimality.
AB - We present new complexity results on the class of 0/1/All constraints. The central idea involves functional elimination, a general method of elimination whose focus is on the subclass of functional constraints. One result is that for the subclass of 'All' constraints, strong n-consistency and minimality is achievable in O(en) time, where e, n are the number of constraints and variables. The main result is that we can solve 0/1/All constraints in O(e(d + n)) time, where d is the domain size. This is an improvement over known results, which are O(ed(d + n)). Furthermore, our algorithm also achieves strong n-consistency and minimality.
UR - http://www.scopus.com/inward/record.url?scp=0032596638&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0032596638
SN - 0262511061
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 175
EP - 180
BT - Proceedings of the National Conference on Artificial Intelligence
PB - AAAI
T2 - Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99)
Y2 - 18 July 1999 through 22 July 1999
ER -