Functional elimination and 0/1/All constraints

Yuanlin Zhang, Roland H.C. Yap, Joxan Jaffar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the National Conference on Artificial Intelligence
PublisherAAAI
Pages175-180
Number of pages6
ISBN (Print)0262511061
StatePublished - 1999
EventProceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99) - Orlando, FL, USA
Duration: Jul 18 1999Jul 22 1999

Publication series

NameProceedings of the National Conference on Artificial Intelligence

Conference

ConferenceProceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99)
CityOrlando, FL, USA
Period07/18/9907/22/99

Cite this

Zhang, Y., Yap, R. H. C., & Jaffar, J. (1999). Functional elimination and 0/1/All constraints. In Proceedings of the National Conference on Artificial Intelligence (pp. 175-180). (Proceedings of the National Conference on Artificial Intelligence). AAAI.