A filtering process for general constraint-satisfaction problems: achieving pairwise-consistency using an associated binary representation
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 420-427
- https://doi.org/10.1109/tai.1989.65349
Abstract
Considers the use of a partial consistency, issuing from relational database theory, within the constraint-satisfaction problems (CSPs) framework, i.e., pairwise consistency. This partial consistency concerns general CSPs (i.e., CSPs the constraints of which may involve more than two variables). The authors provide a polynomial algorithm for achieving this consistency; then they extend the class of polynomially solvable CSPs. This algorithm is based on a minimal binary representation of a general CSP.Keywords
This publication has 11 references indexed in Scilit:
- Network-based heuristics for constraint-satisfaction problemsArtificial Intelligence, 1987
- Arc and path consistency revisitedArtificial Intelligence, 1986
- The complexity of some polynomial network consistency algorithms for constraint satisfaction problemsArtificial Intelligence, 1985
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic HypergraphsSIAM Journal on Computing, 1984
- On the Desirability of Acyclic Database SchemesJournal of the ACM, 1983
- A Sufficient Condition for Backtrack-Free SearchJournal of the ACM, 1982
- Power of Natural SemijoinsSIAM Journal on Computing, 1981
- Increasing tree search efficiency for constraint satisfaction problemsArtificial Intelligence, 1980
- Synthesizing constraint expressionsCommunications of the ACM, 1978
- Networks of constraints: Fundamental properties and applications to picture processingInformation Sciences, 1974