Change search
ReferencesLink to record
Permanent link

Direct link
Maintaining Generalized Arc Consistency on Ad-hoc n-ary Boolean Constraints
Number of Authors: 2
2006 (English)Report (Refereed)
Abstract [en]

Binary decision diagrams (BDDs) can compactly represent ad-hoc n-ary Boolean constraints. However, there is no generalized arc consistency (GAC) algorithm which exploit BDDs. For example, the global case constraint by SICStus Prolog for ad-hoc constraints is designed for non-Boolean domains. In this paper, we introduce a new GAC algorithm, bddc, for BDD constraints. Our empirical results demonstrate the advantages of a new BDD-based global constraint -- bddc is more efficient both in terms of memory and time than the case constraint when dealing with ad-hoc Boolean constraints. This becomes important as the size of the ad-hoc constraints becomes large.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2006, 1. , 6 p.
Series
SICS Technical Report, ISSN 1100-3154 ; 2006:12
Keyword [en]
constraint programming, CSP, BDD, generalized arc consistency
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22026OAI: oai:DiVA.org:ri-22026DiVA: diva2:1041568
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(250 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 250 kBChecksum SHA-512
d678044b02962bf2ca4f03fea420deb376aa00d3015addd3b78704b724fda8323289fa1f047af2d4bea7676336f403d3614cfe2c567b924d12c7ca552dadcc00
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link