Equivariant algorithms for constraint satisfaction problems over coset templates
From MaRDI portal
Publication:344534
DOI10.1016/j.ipl.2016.09.009zbMath1392.68386arXiv1412.4020OpenAlexW2963683868MaRDI QIDQ344534
Publication date: 23 November 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.4020
combinatorial problemsconstraint satisfaction problemsbounded widthcoset templateslocal consistency algorithms
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Descriptive complexity and finite models (68Q19)
Cites Work
- Unnamed Item
- Bounded width problems and algebras
- Affine systems of equations and counting infinitary logic
- An optimal lower bound on the number of variables for graph identification
- Arities of permutation groups: Wreath products and \(k\)-sets
- The collapse of the bounded width hierarchy
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Constraint Satisfaction Problems of Bounded Width
- Turing Machines with Atoms
- Generalized Majority-Minority Operations are Tractable
- A Simple Algorithm for Mal'tsev Constraints