Domain permutation reduction for constraint satisfaction problems
From MaRDI portal
Publication:2389649
DOI10.1016/j.artint.2007.12.001zbMath1183.68309OpenAlexW1995102370MaRDI QIDQ2389649
David A. Cohen, Martin J. Green
Publication date: 17 July 2009
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2007.12.001
complexityNP-completenessCSPconstraint satisfaction problemtractabilitystable marriagerenamable Horn
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Tractability in constraint satisfaction problems: a survey ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Broken-Triangle Property with Adjoint Values ⋮ A polynomial relational class of binary CSP ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hypertree decompositions and tractable queries
- A dichotomy theorem for maximum generalized satisfiability problems.
- Network-based heuristics for constraint-satisfaction problems
- Tree clustering for constraint networks
- Reasoning about qualitative temporal information
- Consistency in networks of relations
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Constraint satisfaction over connected row-convex constraints
- Decomposing constraint satisfaction problems using database techniques
- Foundations of artificial intelligence
- On renamable Horn and generalized Horn functions
- A comparison of structural CSP decomposition methods
- Tractable decision for a constraint language implies tractable search
- Implementing a test for tractability
- Networks of constraints: Fundamental properties and applications to picture processing
- Maximum renamable Horn sub-CNFs
- Triangulated graphs and the elimination process
- Building tractable disjunctive constraints
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Recognizing disguised NR(1) instances of the satisfiability problem
- Renaming a Set of Clauses as a Horn Set
- Extended Horn sets in propositional logic
- On the minimality and global consistency of row-convex constraint networks
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Principles and Practice of Constraint Programming – CP 2003
- Principles and Practice of Constraint Programming – CP 2003
- College Admissions and the Stability of Marriage
- Tractable constraints on ordered domains
