Constraint Satisfaction Problems on Intervals and Lengths

DOI10.1137/S0895480102410201MaRDI QIDQ4652603zbMATH OpenFDO

Authors Andrei Krokhin, Peter Jonsson, P. Jeavons

Publication date 28 February 2005

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

Full work available at URL http://durham-repository.worktribe.com/output/1597056

zbMATH Keywords

Allen's interval algebracomputational complexitydichotomy theoreminterval satisfiabilitytractable cases

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) 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)

Recommendations

• The complexity of constraints on intervals and lengths
• Satisfiability problems on intervals and unit intervals
• On the combination of interval constraint solvers
• Constraint satisfaction problems over the integers with successor
• Constraint satisfaction problems over numeric domains
• Constraint Satisfaction
• Constraint satisfaction problems: complexity and algorithms

Cited in

(16)

• Satisfiability problems on intervals and unit intervals
• Constraint-directed search for all-interval series
• Automated design of fractional PI QFT controller using interval constraint satisfaction technique (ICST)
• Betweenness parameterized above tight lower bound
• On subbetweennesses of trees: hardness, algorithms, and characterizations
• Tractability in constraint satisfaction problems: a survey
• On satisfiability problems with a linear structure
• The complexity of constraints on intervals and lengths
• Interval graph representation with given interval and intersection lengths
• QFT prefilter design for multivariable systems using interval constraint satisfaction technique
• Analytic constraint solving and interval arithmetic
• Interval graphs with side (and size) constraints
• Solving infinite-domain CSPs using the patchwork property
• Characterization and representation problems for intersection betweennesses
• Strict betweennesses induced by posets as well as by graphs
• Complexity classification in qualitative temporal constraint reasoning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4652603)