The Library
Constraint satisfaction problems on intervals and lengths
Tools
UNSPECIFIED. (2004) Constraint satisfaction problems on intervals and lengths. SIAM JOURNAL ON DISCRETE MATHEMATICS, 17 (3). pp. 453477. ISSN 08954801
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/S0895480102410201
Abstract
We study intervalvalued 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 wellknown 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 intervalvalued 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 NPcomplete.
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 NPcomplete.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Journal or Publication Title:  SIAM JOURNAL ON DISCRETE MATHEMATICS  
Publisher:  SIAM PUBLICATIONS  
ISSN:  08954801  
Official Date:  2004  
Dates: 


Volume:  17  
Number:  3  
Number of Pages:  25  
Page Range:  pp. 453477  
Identification Number:  10.1137/S0895480102410201  
Publication Status:  Published  
URI:  http://wrap.warwick.ac.uk/id/eprint/8534 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 