ECCC-Report TR01-077https://eccc.weizmann.ac.il/report/2001/077Comments and Revisions published for TR01-077en-usTue, 13 Nov 2001 08:45:15 +0200
Paper TR01-077
| The complexity of constraints on intervals and lengths |
Andrei Krokhin,
Peter Jeavons,
Peter Jonsson
https://eccc.weizmann.ac.il/report/2001/077We 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 such CSPs.
One intersting question concerning such problems is to determine exactly
how the complexity of an interval-valued CSP depends on the set of
constraints allowed in instances. For the framework known as Allen's
interval algebra this question was completely answered earlier by the
authors by giving a complete description of the tractable cases and
showing that all remaining cases are NP-complete.
Tue, 13 Nov 2001 08:45:15 +0200https://eccc.weizmann.ac.il/report/2001/077