There are no pure relational width 2 constraint satisfaction problems
type: Item
instance of: scholarly article
title: There are no pure relational width 2 constraint satisfaction problems
zbMATH Open document ID: 1191.68339
published in: Information Processing Letters
publication date: 2010-06-16T00:00:00Z
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5721974
zbMATH Keywords: computational complexity
zbMATH Keywords: constraint satisfaction problems
author: Víctor Dalmau
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.10.005
OpenAlex ID: W2123895606
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: Combinatorial problems raised from 2-semilattices
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Dualities for Constraint Satisfaction Problems
cites work: Recent Results on the Algebraic Approach to the CSP
cites work: Q4495111
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Tractability and Learnability Arising from Algebras with Few Subpowers
cites work: On tractability and congruence distributivity
cites work: Chromatically optimal rigid graphs
cites work: A Subalgebra Intersection Property for Congruence Distributive Varieties
DOI: 10.1016/J.IPL.2008.10.005
description: scientific article; zbMATH DE number 5721974