A polynomial relational class of binary CSP

DOI10.1007/S10472-017-9566-6MaRDI QIDQ722101zbMATH OpenOpenAlexFDO

Authors Wafa Jguirim, Wady Naanaa, 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

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)

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

Cites work

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

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)