Can I read The Complexity of Global Cardinality Constraints on EtoBox?

The Complexity of Global Cardinality Constraints by Bulatov, Andrei A.; Marx, Daniel is a scholarly article available to read on EtoBox.

What is The Complexity of Global Cardinality Constraints about?

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(G), the constraint satisfaction problem with global cardinality constraints that allows only relations from the set G. The main result of this paper characterizes sets G that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.

Author

Bulatov, Andrei A.; Marx, Daniel

Published

2010

Language

EN