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

Direct link
The Complexity of Constraints on Intervals and Lengths
Oxford University computing Laboratory.
Oxford University computing Laboratory.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2002 (English)In: Proc. of the 19th Int'l Symposium on Theoretical Aspects of Computer Science (STACS-2002)', 2002, 443-454 p.Conference paper (Refereed)
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 ofvariables subject to constraints on the relative positions of intervals.Many well-known problems such as Interval Graph Recognitionand Interval Satisfiability can be considered as examples of such CSPs.One intersting question concerning such problems is to determine exactlyhow 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 andshowing that all remaining cases are NP-complete.

Place, publisher, year, edition, pages
2002. 443-454 p.
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-61728OAI: diva2:370706
Available from: 2010-11-17 Created: 2010-11-17 Last updated: 2010-11-26

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and Technology

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

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link