All reports by Author Andrei Bulatov:

__
TR02-034
| 18th April 2002
__

Andrei Bulatov#### Mal'tsev constraints are tractable

__
TR02-032
| 17th April 2002
__

Andrei Bulatov#### Tractable Constraint Satisfaction Problems on a 3-element set

Andrei Bulatov

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>