On binary constraint problems
From MaRDI portal
Publication:4305669
DOI10.1145/176584.176585zbMATH Open0813.03045OpenAlexW2090310951MaRDI QIDQ4305669
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
algorithmsrelation algebrasbinary constraint satisfaction problemsmatrices of relationspath- consistency
Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Cylindric and polyadic algebras; relation algebras (03G15)
Cited In (39)
- Relation algebras of Sugihara, Belnap, Meyer, and Church
- Non-local configuration of component interfaces by constraint satisfaction
- 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
- Hardness of Network Satisfaction for Relation Algebras with Normal Representations
- Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure
- 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
- Probabilistic temporal networks: A unified framework for reasoning with time and uncertainty
- Tractable approximations for temporal constraint handling
- Relational proof systems for spatial reasoning ★
- Temporal constraint networks
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- Binary constraint satisfaction problems defined by excluded topological minors
- 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
- Satisfying constraint sets through convex envelopes
- Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
- 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
- From points to intervals
- The complexity of constraint satisfaction problems for small relation algebras
- Combining topological and size information for spatial reasoning
- Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
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)
