Journal article icon

Journal article

Constraint satisfaction problems on intervals and lengths

Abstract:

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

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1137/S0895480102410201

Authors


Krokhin, A More by this author
Jeavons, P More by this author
Jonsson, P More by this author
Journal:
SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume:
17
Issue:
3
Pages:
453-477
Publication date:
2004
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
URN:
uuid:be5b3375-6a6c-400f-8356-5e831d94bca0
Source identifiers:
328630
Local pid:
pubs:328630

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP