Tractable structures for constraint satisfaction with truth tables
type: Item
instance of: scholarly article
title: Tractable structures for constraint satisfaction with truth tables
zbMATH Open document ID: 1253.68180
author: Dániel Marx
published in: Theory of Computing Systems
publication date: 2011-05-23T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1807/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5898926
zbMATH Keywords: computational complexity
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: treewidth
zbMATH Keywords: adaptive width
MaRDI profile type: Publication
OpenAlex ID: W2067706177
cites work: Q5469338
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: The complexity of maximal constraint languages
cites work: Constraint satisfaction with succinctly specified relations
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Hypertree decompositions and tractable queries
cites work: Fixed-parameter complexity in AI and nonmonotonic reasoning
cites work: The Structure of Tractable Constraint Satisfaction Problems
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: Constraint solving via fractional edge covers
cites work: When is the evaluation of conjunctive queries tractable?
cites work: Which problems have strongly exponential complexity?
cites work: Closure properties of constraints
cites work: Conjunctive-query containment and constraint satisfaction
cites work: Q3002818
cites work: Approximating fractional hypertree width
cites work: Uniform Constraint Satisfaction Problems and Database Theory
cites work: The complexity of satisfiability problems
DOI: 10.1007/S00224-009-9248-9
description: scientific article; zbMATH DE number 5898926