GCC-like Restrictions on the Same constraint

Beldiceanu, Nicolas; Katriel, Irit; Thiel, Sven; Faltings, Boi; Petcu, Adrian; Fages, Francois; Rossi, Francesca

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

GCC-like Restrictions on the Same constraint

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

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Beldiceanu, N., Katriel, I., & Thiel, S. (2005). GCC-like Restrictions on the Same constraint. In Constraint Satisfaction and Constraint Logic Programming: ERCIM/CoLogNet International Workshop, CSCLP 2004 (pp. 1-11). Berlin, Germany: Springer.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-269F-7

要旨

The \Same\ constraint takes two sets of variables $X$ and $Z$ such that $|X|=|Z|$ and assigns values to them such that the multiset of values assigned to the variables in $X$ is equal to the multiset of values assigned to the variables in $Z$. In this paper we extend the \Same\ constraint in a GCC-like manner by adding cardinality requirements on the values. That is, for each value we have a lower and upper bound on the number of variables that can be assigned this value. We show an algorithm that achieves arc-consistency for this constraint and a faster algorithm that achieves bound-consistency for a restricted case of it.