Constraint Satisfaction Problems Solvable by Local Consistency Methods
From MaRDI portal
Recommendations
- Locally consistent constraint satisfaction problems
- Automata, Languages and Programming
- Graph-Theoretic Concepts in Computer Science
- Locally finite constraint satisfaction problems
- Local consistency and SAT-solvers
- A general approach for constraint solving by local search
- Limit Behavior of Locally Consistent Constraint Satisfaction Problems
- Local Search and Constraint Programming
Cites work
- scientific article; zbMATH DE number 1670830 (Why is no real title available?)
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- A Simple Algorithm for Mal'tsev Constraints
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Closure properties of constraints
- Combinatorial problems raised from 2-semilattices
- Congruence distributivity implies bounded width
- Constraint Satisfaction Problems of Bounded Width
- Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited
- Dualities for Constraint Satisfaction Problems
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- On tractability and congruence distributivity
- Recent Results on the Algebraic Approach to the CSP
- Robust satisfiability of constraint satisfaction problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The collapse of the bounded width hierarchy
- The complexity of the conservative generalized satisfiability problem
- The structure of finite algebras
- Tractability and learnability arising from algebras with few subpowers
- Universal algebra and hardness results for constraint satisfaction problems
- Varieties with few subalgebras of powers
Cited in
(89)- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- The number of clones determined by disjunctions of unary relations
- Proof Complexity Meets Algebra
- Tractability of quantified temporal constraints to the max
- P. van Beek and R. Dechter's theorem on constraint looseness and local consistency
- Quantum advantage and CSP complexity
- Parameterized complexity of the workflow satisfiability problem
- Local consistency as a reduction between constraint satisfaction problems
- Algebraic approach to approximation
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- On the descriptive complexity of temporal constraint satisfaction problems
- Tractability in constraint satisfaction problems: a survey
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Locally consistent constraint satisfaction problems
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- On singleton arc consistency for CSPs defined by monotone patterns
- On singleton arc consistency for CSPs defined by monotone patterns
- Idempotent n-permutable varieties.
- The power of linear programming for general-valued CSPs
- Dichotomy for finite tournaments of mixed-type
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Backdoors into heterogeneous classes of SAT and CSP
- On a stronger reconstruction notion for monoids and clones
- Constants and finite unary relations in qualitative constraint reasoning
- Automata, Languages and Programming
- Limit Behavior of Locally Consistent Constraint Satisfaction Problems
- A polynomial relational class of binary CSP
- Constant-query testability of assignments to constraint satisfaction problems
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- The power of Sherali-Adams relaxations for general-valued CSPs
- Backdoor sets for CSP
- A complexity dichotomy in spatial reasoning via Ramsey theory
- A finite-model-theoretic view on propositional proof complexity
- scientific article; zbMATH DE number 7536113 (Why is no real title available?)
- CLAP: A New Algorithm for Promise CSPs
- Network satisfaction problems solved by k-consistency
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- A general approach for constraint solving by local search
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- \( \omega \)-categorical structures avoiding height 1 identities
- Binarisation for valued constraint satisfaction problems
- The complexity of general-valued CSPs
- Ivo G. Rosenberg's work on maximal clones and minimal clones
- Hybrid tractable classes of constraint problems
- Constraint satisfaction problems over numeric domains
- Datalog-expressibility for monadic and guarded second-order logic
- Smooth approximations and relational width collapses
- Sherali-Adams relaxations for valued CSPs
- Necessary conditions for tractability of valued CSPs
- The smallest hard trees
- Sensitive instances of the constraint satisfaction problem
- Satisfiability in MultiValued Circuits
- Solving CSPs using weak local consistency
- Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Promise and infinite-domain constraint satisfaction
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Graphs of finite algebras: edges, and connectivity
- Characterizations of several Maltsev conditions.
- The Complexity of Boolean Surjective General-Valued CSPs
- Quantum advantage and CSP complexity
- A Galois connection for valued constraint languages of infinite size
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Graph-Theoretic Concepts in Computer Science
- Equivariant algorithms for constraint satisfaction problems over coset templates
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Limits of symmetric computation (invited talk)
- The complexity of valued CSPs
- Mal'tsev conditions, lack of absorption, and solvability.
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- The wonderland of reflections
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Approximate graph colouring and the hollow shadow
- SDPs and robust satisfiability of promise CSP
- Datalog-expressibility for monadic and guarded second-order logic
- DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS
- Undefinability of approximation of 2-to-2 games
- Deciding absorption in relational structures
- Learnability of solutions to conjunctive queries
- Absorption in universal algebra and CSP
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- Approximate graph coloring and the crystal with a hollow shadow
- Robust algorithms with polynomial loss for near-unanimity CSPs
- A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Constraint satisfaction problem: what makes the problem easy
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
This page was built for publication: Constraint Satisfaction Problems Solvable by Local Consistency Methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189638)
