Constraint Satisfaction Problems on Intervals and Lengths

DOI10.1137/S0895480102410201zbMath1101.68043MaRDI QIDQ4652603

Andrei A. Krokhin, Peter Jonsson, Peter G. Jeavons

Publication date: 28 February 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexitydichotomy theoremtractable casesAllen's interval algebrainterval satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Tractability in constraint satisfaction problems: a survey ⋮ Automated design of fractional PI QFT controller using interval constraint satisfaction technique (ICST) ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Characterization and representation problems for intersection betweennesses ⋮ On subbetweennesses of trees: hardness, algorithms, and characterizations ⋮ Strict betweennesses induced by posets as well as by graphs ⋮ Betweenness parameterized above tight lower bound ⋮ Interval graph representation with given interval and intersection lengths ⋮ QFT prefilter design for multivariable systems using interval constraint satisfaction technique ⋮ Complexity classification in qualitative temporal constraint reasoning

This page was built for publication: Constraint Satisfaction Problems on Intervals and Lengths