The complexity of global cardinality constraints

DOI10.2168/LMCS-6(4:4)2010zbMath1202.68208arXiv1010.0201MaRDI QIDQ3064168

Dániel Marx, Andrei A. Bulatov

Publication date: 20 December 2010

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.0201

zbMATH Keywords

complexitycardinality constraintsconstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

The power of propagation: when GAC is enough ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Unnamed Item ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Uses Software

• CCSP

This page was built for publication: The complexity of global cardinality constraints