4 citations · 11 across the 8 of their papers we have counts for
8 papers
Faster algorithms for graph homomorphism via tractable constraint satisfaction
Clément Carbonnel
We show that the existence of a homomorphism from an -vertex graph to an -vertex graph can be decided in time and polynomial space if comes fro…
Partial Queries for Constraint Acquisition
Christian Bessiere, Clement Carbonnel, Anton Dries +8
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the us…
Point-width and Max-CSPs
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs…
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…
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…
Propagation via Kernelization: The Vertex Cover Constraint
Clément Carbonnel, Emmanuel Hébrard
The technique of kernelization consists in extracting, from an instance of a problem, an essentially equivalent instance whose size is bounded in a parameter k. Besides being the b…
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
Clément Carbonnel
Given a fixed constraint language , the conservative CSP over (denoted by c-CSP()) is a variant of CSP() where the domain of each variable can be restricted arbitraril…
On Backdoors To Tractable Constraint Languages
Clement Carbonnel, Martin C. Cooper, Emmanuel Hebrard
In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the pr…