101 citations · 355 across the 29 of their papers we have counts for
Showing 2010 · cs.CCShow all
3 papers · 2 filters
cs.CC2010★ 5 cited
A dichotomy theorem for conservative general-valued CSPs
Vladimir Kolmogorov
We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions over…
cs.CC2010★ 6 cited
Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
Vladimir Kolmogorov, Stanislav Zivny
We study optimisation problems that can be formulated as valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fix…
cs.CC2010★ 8 cited
The complexity of conservative finite-valued CSPs
Vladimir Kolmogorov, Stanislav Zivny
We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions over…