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. 
Jaffar, Joxan 
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
ISBN: 0262511061
Appears in Collections:Staff Publications

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

Google ScholarTM



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