Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39265
Title: Functional elimination and 0/1/All constraints
Authors: Zhang, Yuanlin 
Yap, Roland H.C. 
Jaffar, Joxan 
Issue Date: 1999
Source: 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.

Page view(s)

46
checked on Dec 8, 2017

Google ScholarTM

Check


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