Classifying the complexity of constraints using finite algebras

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed...

Täydet tiedot

Bibliografiset tiedot
Päätekijät: Bulatov, A, Jeavons, P, Krokhin, A
Aineistotyyppi: Journal article
Kieli:English
Julkaistu: 2005