System disruptions
We are currently experiencing disruptions on the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint
RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
RISE, Swedish ICT, SICS, Computer Systems Laboratory.ORCID iD: 0000-0003-3079-8095
2001 (English)Conference paper, Published paper (Refereed)
Abstract [en]

We first present a generic pruning technique, which aggregates several constraints sharing some variables. The method is derived from an idea called sweep, which is extensively used, in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. We then specialise this technique to the non-overlapping rectangles constraint, describe several optimisations, and give an empirical evaluation based on six sets of test instances with different characteristics.

Place, publisher, year, edition, pages
2001, 1.
Series
LNCS ; 2239
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-22593DOI: 10.1007/3-540-45578-7_26OAI: oai:DiVA.org:ri-22593DiVA, id: diva2:1042158
Conference
Principles and Practice of Constraint Programming (CP 2001): 7th International Conference, 26 Nov - 1 Dec 2001, Paphos, Cyprus
Note

DOI 10.1007/3-540-45578-7_26. Preprint available as SICS Technical Report T2001-13.

Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-05-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttp

Authority records

Carlsson, Mats

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
SICSComputer Systems Laboratory
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 361 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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