Access Restriction

Author Bulatov, Andrei A. ♦ Marx, Dániel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(Γ), the CSP with global cardinality constraints that allows only relations from the set Γ. The main result of this paper characterizes sets Γ that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.
Description Affiliation: Tel Aviv University, Tel Aviv, Israel (Marx, Dániel) || Simon Fraser Univerity, Burnaby, BC, Canada (Bulatov, Andrei A.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 53
Issue Number 9
Page Count 8
Starting Page 99
Ending Page 106

Open content in new tab

   Open content in new tab
Source: ACM Digital Library