A Simple Algorithm for Mal'tsev Constraints
From MaRDI portal
Publication:5470744
DOI10.1137/050628957zbMath1112.08002OpenAlexW1983032729MaRDI QIDQ5470744
Andrei A. Bulatov, Victor Dalmau
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6b8bd3234711967dd50e56196df9f48cd040da75
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Tractability in constraint satisfaction problems: a survey, CLAP: A New Algorithm for Promise CSPs, Hard constraint satisfaction problems have hard gaps at location 1, The complexity of constraint satisfaction games and QCSP, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Equivariant algorithms for constraint satisfaction problems over coset templates, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Is Polynomial Time Choiceless?, Unnamed Item, Unnamed Item, Unnamed Item, A new line of attack on the dichotomy conjecture, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Maltsev digraphs have a majority polymorphism, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property, Binarisation for Valued Constraint Satisfaction Problems, Colouring, constraint satisfaction, and complexity, On the number of finite algebraic structures, The Complexity of Valued CSPs, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, Counting Constraint Satisfaction Problems., Varieties with few subalgebras of powers, On singleton arc consistency for CSPs defined by monotone patterns, THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS, On Maltsev Digraphs, On the CSP Dichotomy Conjecture, Solving equation systems in ω-categorical algebras, Quantified constraint satisfaction and the polynomially generated powers property, On Maltsev digraphs, Constraint satisfaction problems over semilattice block Mal'tsev algebras, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Parameterized Complexity of the Workflow Satisfiability Problem, Backdoors into heterogeneous classes of SAT and CSP, Affine systems of equations and counting infinitary logic, Relatively quantified constraint satisfaction, Unnamed Item, Recent Results on the Algebraic Approach to the CSP, Constraint Satisfaction Problems with Infinite Templates, Commutative idempotent groupoids and the constraint satisfaction problem.
