77 citations · 733 across the 54 of their papers we have counts for
5 papers · 1 filter
The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau, Kolaiti…
The Complexity of Counting Surjective Homomorphisms and Compactions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertic…
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Clement Carbonnel, David A. Cohen, Martin C. Cooper +1
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of…
The complexity of Boolean surjective general-valued CSPs
Peter Fulla, Hannes Uppman, Stanislav Zivny
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a -valued objective function given as a sum of fixed-arity funct…
Discrete Convexity in Joint Winner Property
Yuni Iwamasa, Kazuo Murota, Stanislav Zivny
In this paper, we reveal a relation between joint winner property (JWP) in the field of valued constraint satisfaction problems (VCSPs) and M-convexity in the field of…