On binary constraint problems

DOI10.1145/176584.176585MaRDI QIDQ4305669zbMATH OpenOpenAlexFDO

Authors Peter B. Ladkin, Roger Maddux

Publication date 7 June 1995

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/176584.176585

zbMATH Keywords

algorithmsrelation algebrasbinary constraint satisfaction problemsmatrices of relationspath- consistency

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Cylindric and polyadic algebras; relation algebras (03G15)

Recommendations

• Fast algebraic methods for interval constraint problems
• Constraint satisfaction -- algorithms and complexity analysis
• Constraints, consistency and closure
• Characterising tractable constraints

Cited in

(41)

• Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
• Non-local configuration of component interfaces by constraint satisfaction
• Relation algebras of Sugihara, Belnap, Meyer, and Church
• GNet: a generalized network model and its applications in qualitative spatial reasoning
• An algebraic characterization of tractable constraints
• Algebraic foundations for qualitative calculi and networks
• On point-duration networks for temporal reasoning
• Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Backtracking algorithms for disjunctions of temporal constraints
• Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class
• A condensed semantics for qualitative spatial reasoning about oriented straight line segments
• Qualitative reasoning about relative direction of oriented points
• scientific article; zbMATH DE number 4172390 (Why is no real title available?)
• Probabilistic temporal networks: A unified framework for reasoning with time and uncertainty
• Tractable approximations for temporal constraint handling
• Temporal constraint networks
• Binary constraint satisfaction problems defined by excluded topological minors
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Reasoning about qualitative temporal information
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• A relation-algebraic approach to the region connection calculus
• A new approach to cyclic ordering of 2D orientations using ternary relation algebras
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• Relation algebras of intervals
• So, what exactly is a qualitative calculus?
• Relation algebras and their application in temporal and spatial reasoning
• Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
• Satisfying constraint sets through convex envelopes
• Graph-Theoretic Concepts in Computer Science
• RCC8 binary constraint network can be consistently extended
• Combinatorial problems raised from 2-semilattices
• Efficient algorithms for qualitative reasoning about time
• Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra
• On point-based temporal disjointness
• Relational proof systems for spatial reasoning
• From points to intervals
• Constraint satisfaction problem with bilevel constraint: Application to interpretation of over-segmented images
• The complexity of constraint satisfaction problems for small relation algebras
• Combining topological and size information for spatial reasoning

This page was built for publication: On binary constraint problems

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