Filtering Algorithms for the Same and UsedBy Constraints

Beldiceanu, Nicolas; Katriel, Irit; Thiel, Sven

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Filtering Algorithms for the Same and UsedBy Constraints

MPS-Authors

/persons/resource/persons44744

Katriel, Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45615

Thiel, Sven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Beldiceanu, N., Katriel, I., & Thiel, S. (2006). Filtering Algorithms for the Same and UsedBy Constraints. Archives of Control Sciences, 16(2), 191-220.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-248D-1

Abstract

We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the variables in $Z$ is contained in the multiset of values assigned to the variables in $X$. \Same\ is the special case of \UsedBy\ in which $|X|=|Z|$. We show algorithms that achieve arc-consistency and bound-consistency for these constraints.