Please use this identifier to cite or link to this item:
|Title:||Functional elimination and 0/1/All constraints||Authors:||Zhang, Yuanlin
Yap, Roland H.C.
|Issue Date:||1999||Citation:||Zhang, Yuanlin,Yap, Roland H.C.,Jaffar, Joxan (1999). Functional elimination and 0/1/All constraints. Proceedings of the National Conference on Artificial Intelligence : 175-180. ScholarBank@NUS Repository.||Abstract:||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.||Source Title:||Proceedings of the National Conference on Artificial Intelligence||URI:||http://scholarbank.nus.edu.sg/handle/10635/39265||ISBN:||0262511061|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.