All reports by Author Peter Jonsson:

__
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

__
TR99-038
| 27th August 1999
__

Peter Jonsson, Paolo Liberatore#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

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 >>>

Peter Jonsson, Paolo Liberatore

We study the computational complexity of an optimization

version of the constraint satisfaction problem: given a set $F$ of

constraint functions, an instance consists of a set of variables $V$

related by constraints chosen from $F$ and a natural number $k$. The

problem is to decide whether there exists a ...
more >>>