Concepedia

Constraint Satisfaction Problems of Bounded Width

Libor Barto, Marcin Kozik

2009 · 152 citations · 14 references

DOI

Concepts

Abstract

We provide a full characterization of applicability of The Local Consistency Checking algorithm to solving the non-uniform Constraint Satisfaction Problems. This settles the conjecture of Larose and Zadori.

References

14

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Tomás Feder, Moshe Y. Vardi · SIAM Journal on Computing · 1998 · 1.1K citations

, , +15

Classifying the Complexity of Constraints Using Finite Algebras

Andreĭ A. Bulatov, Peter Jeavons, Andrei Krokhin · SIAM Journal on Computing · 2005 · 580 citations · Full text

, , +17

Closure properties of constraints

Peter Jeavons, David A. Cohen, Marc Gyssens · Journal of the ACM · 1997 · 498 citations · Full text

, , +12

A dichotomy theorem for constraint satisfaction problems on a 3-element set

Andreǐ A. Bulatov · Journal of the ACM · 2006 · 372 citations

, , +15

Tractable conservative constraint satisfaction problems

2003 · 238 citations

, , +11