Tractable structures for constraint satisfaction with truth tables
From MaRDI portal
Publication:537902
DOI10.1007/s00224-009-9248-9zbMath1253.68180MaRDI QIDQ537902
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/
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, On the complexity of existential positive queries, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Tractability in constraint satisfaction problems: a survey
Cites Work
- 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
- Approximating fractional hypertree width
- 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