52 citations · 146 across the 26 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.LO2010★ 21 cited
The complexity of global cardinality constraints
Andrei A. Bulatov, Daniel Marx
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 add…
cs.CC2010★ 52 cited
The complexity of weighted and unweighted #CSP
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +3
We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our red…