Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

GCC-like Restrictions on the Same constraint

MPG-Autoren
/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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-269F-7
Zusammenfassung
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.