Tractable structures for constraint satisfaction with truth tables

DOI10.1007/s00224-009-9248-9zbMath1253.68180OpenAlexW2067706177MaRDI QIDQ537902

Dániel Marx

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1807/

zbMATH Keywords

computational complexitytreewidthconstraint satisfactionadaptive width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Tractability in constraint satisfaction problems: a survey ⋮ On the complexity of existential positive queries ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• Conjunctive-query containment and constraint satisfaction
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Which problems have strongly exponential complexity?
• Constraint satisfaction with succinctly specified relations
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• When is the evaluation of conjunctive queries tractable?
• The complexity of maximal constraint languages
• The complexity of satisfiability problems
• Uniform Constraint Satisfaction Problems and Database Theory
• The Structure of Tractable Constraint Satisfaction Problems

This page was built for publication: Tractable structures for constraint satisfaction with truth tables