A polynomial relational class of binary CSP

DOI10.1007/S10472-017-9566-6zbMATH Open1484.68071OpenAlexW2766016802MaRDI QIDQ722101FDOQ722101

Wady Naanaa, Wafa Jguirim, M. C. Cooper

Publication date: 20 July 2018

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://oatao.univ-toulouse.fr/22115/1/Jguirim_22115.pdf

Recommendations

• Characterising tractable constraints
• Tractability by approximating constraint languages
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• New tractable classes from old
• Tractability in constraint satisfaction problems: a survey

zbMATH Keywords

polymorphismtractable languageconstraint satisfaction problemmajority operations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• Network-based heuristics for constraint-satisfaction problems
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Constraint satisfaction over connected row-convex constraints
• A comparison of structural CSP decomposition methods
• Domain permutation reduction for constraint satisfaction problems
• An optimal coarse-grained arc consistency algorithm
• Tractability in constraint satisfaction problems: a survey
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Arc consistency and friends
• Tractable constraints on ordered domains
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• A sufficient condition for backtrack-bounded search
• An optimal k-consistency algorithm
• Near Unanimity Constraints Have Bounded Pathwidth Duality

Cited In (1)

• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice

This page was built for publication: A polynomial relational class of binary CSP

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