Decomposing constraint satisfaction problems using database techniques
From MaRDI portal
Publication:1321054
DOI10.1016/0004-3702(94)90003-5zbMath0803.68090OpenAlexW1978282744MaRDI QIDQ1321054
Marc Gyssens, David A. Cohen, Peter G. Jeavons
Publication date: 2 January 1995
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(94)90003-5
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Structural tractability of counting of solutions to conjunctive queries, Partition search for non-binary constraint satisfaction, Domain permutation reduction for constraint satisfaction problems, Accelerating new product development by overcoming complexity constraints, On minimal constraint networks, Weighted hypertree decompositions and optimal query plans, An algebraic characterization of tractable constraints, Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width., The power of propagation: when GAC is enough, STR2: optimized simple tabular reduction for table constraints, Combining restarts, nogoods and bag-connected decompositions for solving csps, Learning cluster-based structure to solve constraint satisfaction problems, A unified theory of structural tractability for constraint satisfaction problems, Reformulating table constraints using functional dependencies-an application to explanation generation, Constraint satisfaction -- algorithms and complexity analysis, Hypertree decompositions and tractable queries, On the power of structural decompositions of graph-based representations of constraint problems, A new tractable class of constraint satisfaction problems, Tractable constraints on ordered domains, Tractable constraints on ordered domains, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints, Constraints in vision. Outline of a set-theoretic approach., A fast algorithm for query optimization in universal-relation databases, Constraints, consistency and closure, HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results, Fast and parallel decomposition of constraint satisfaction problems, A Logical Approach to Constraint Satisfaction, Uniform Constraint Satisfaction Problems and Database Theory, A comparison of structural CSP decomposition methods, Conjunctive-query containment and constraint satisfaction, Large hypertree width for sparse random hypergraphs, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, Compiling constraint satisfaction problems, Characterising tractable constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decomposing a relation into a tree of binary relations
- Testing arbitrary subhypergraphs for the lossless join property
- Network-based heuristics for constraint-satisfaction problems
- Constraint satisfaction from a deductive viewpoint
- Tree clustering for constraint networks
- Solving a cutting-stock problem with the constraint logic programming language CHIP
- Generating hinges from arbitrary subhypergraphs
- Consistency in networks of relations
- Counting representable sets on simple graphs
- Networks of constraints: Fundamental properties and applications to picture processing
- The combinatorics of object recognition in cluttered environments using constrained search
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- On the complexity of join dependencies
- A sufficient condition for backtrack-bounded search
- The Consistent Labeling Problem: Part I
- A Sufficient Condition for Backtrack-Free Search
- A simplied universal relation assumption and its properties
- Computing the Minimum Fill-In is NP-Complete
- Synthesizing constraint expressions
- A relational model of data for large shared data banks
