liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Constraint satisfaction problems on intervals and lengths
Computer Science University of Durham.
Computing Laboratory Oxford University.
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2004 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, Vol. 17, no 3, 453-477 p.Article in journal (Refereed) Published
Abstract [en]

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 such CSPs. One interesting 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. Here we extend the qualitative framework of Allen's algebra with additional constraints on the lengths of intervals. We allow these length constraints to be expressed as Horn disjunctive linear relations, a well-known tractable and sufficiently expressive form of constraints. The class of problems we consider contains, in particular, problems that are very closely related to the previously studied UNIT INTERVAL GRAPH SANDWICH problem. We completely characterize sets of qualitative relations for which the CSP augmented with arbitrary length constraints of the above form is tractable. We also show that, again, all the remaining cases are NP-complete.

Place, publisher, year, edition, pages
2004. Vol. 17, no 3, 453-477 p.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-22312DOI: 10.1137/S0895480102410201Local ID: 1506OAI: diva2:242625
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2011-01-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
SIAM Journal on Discrete Mathematics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link