Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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-31Bibliographically approved

Open Access in DiVA

fulltext(250 kB)12 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: 12 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

urn-nbn

Altmetric score

urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.29.0