13 citations · 46 across the 21 of their papers we have counts for
4 papers · 1 filter
A polynomial-time algorithm for median-closed semilinear constraints
Manuel Bodirsky, Marcello Mamino
A subset of Q^n is called semilinear (or piecewise linear) if it is Boolean combination of linear half-spaces. We study the computational complexity of the constraint satisfaction…
The complexity of disjunctive linear Diophantine constraints
Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1
We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.
Fundamental group in o-minimal structures with definable Skolem functions
Bruno Dinis, Mário J. Edmundo, Marcello Mamino
In this paper we work in an arbitrary o-minimal structure with definable Skolem functions and we prove that definably connected, locally definable manifolds are uniformly definably…
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
Manuel Bodirsky, Marcello Mamino, Caterina Viola
Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs dependin…