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.

Page view(s)

checked on Oct 28, 2019

Google ScholarTM



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