On Minimal Constraint Networks
In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove thi...
Main Author: | Gottlob, G |
---|---|
Format: | Journal article |
Language: | English |
Published: |
2011
|
Similar Items
-
On Minimal Constraint Networks
by: Gottlob, G
Published: (2011) -
On Tractable Queries and Constraints
by: Gottlob, G, et al.
Published: (1999) -
Semantic acyclicity under constraints
by: Gottlob, G, et al.
Published: (2016) -
Semantic acyclicity under constraints
by: Barceló, P, et al.
Published: (2016) -
Conditional Constraint Satisfaction: Logical Foundations and Complexity
by: Gottlob, G, et al.
Published: (2007)