Recent Results on the Algebraic Approach to the CSP
From MaRDI portal
Publication:5504700
DOI10.1007/978-3-540-92800-3_4zbMath1171.08300OpenAlexW1511747486MaRDI QIDQ5504700
Andrei A. Bulatov, Matthew A. Valeriote
Publication date: 22 January 2009
Published in: Complexity of Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_4
Related Items (24)
Tractability in constraint satisfaction problems: a survey ⋮ Aggregation of Votes with Multiple Positions on Each Issue ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Testing list \(H\)-homomorphisms ⋮ List-homomorphism problems on graphs and arc consistency ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ Not all nilpotent monoids are finitely related ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ On the CSP Dichotomy Conjecture ⋮ Key (critical) relations preserved by a weak near-unanimity function ⋮ The complexity of the list homomorphism problem for graphs ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ CSP duality and trees of bounded pathwidth ⋮ On algebras with many symmetric operations ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ The number of clones determined by disjunctions of unary relations ⋮ Dualities for Constraint Satisfaction Problems ⋮ Characterizations of several Maltsev conditions. ⋮ Commutative idempotent groupoids and the constraint satisfaction problem. ⋮ Distance constraint satisfaction problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive rate of constraints
- \(H\)-coloring dichotomy revisited
- Bounded width problems and algebras
- Existence theorems for weakly symmetric operations
- On the complexity of H-coloring
- The set of types of a finitely generated variety
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Constraints and universal algebra
- A new tractable class of constraint satisfaction problems
- Few subpowers, congruence distributivity and near-unanimity terms
- Combinatorial problems raised from 2-semilattices
- Tractable Clones of Polynomials over Semigroups
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Varieties with few subalgebras of powers
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of satisfiability problems
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
- Affine Systems of Equations and Counting Infinitary Logic
- A Characterisation of First-Order Constraint Satisfaction Problems
- A Simple Algorithm for Mal'tsev Constraints
- Mathematical Foundations of Computer Science 2005
- Dualities for Constraint Satisfaction Problems
This page was built for publication: Recent Results on the Algebraic Approach to the CSP
