Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PETER JONSSON:
All reports by Author Peter Jonsson:

TR03-062 | 10th July 2003
Andrei Krokhin, Peter Jonsson

Recognizing Frozen Variables in Constraint Satisfaction Problems

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


TR01-077 | 24th September 2001
Andrei Krokhin, Peter Jeavons, Peter Jonsson

The complexity of constraints on intervals and lengths

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


TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

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




ISSN 1433-8092 | Imprint