All reports by Author Andrei Krokhin:

__
TR03-062
| 10th July 2003
__

Andrei Krokhin, Peter Jonsson#### Recognizing Frozen Variables in Constraint Satisfaction Problems

__
TR01-077
| 24th September 2001
__

Andrei Krokhin, Peter Jeavons, Peter Jonsson#### The complexity of constraints on intervals and lengths

Andrei Krokhin, Peter Jonsson

In constraint satisfaction problems over finite domains, some variables

can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the

instances. We show that the complexity of ...
more >>>

Andrei Krokhin, Peter Jeavons, Peter Jonsson

We study interval-valued constraint satisfaction problems (CSPs),

in which the aim is to find an assignment of intervals to a given set of

variables subject to constraints on the relative positions of intervals.

Many well-known problems such as Interval Graph Recognition

and Interval Satisfiability can be considered as examples of ...
more >>>