Constraint satisfaction with succinctly specified relations

DOI10.1016/j.jcss.2010.04.003zbMath1214.68347OpenAlexW2066776015MaRDI QIDQ1959431

Martin Grohe, Hubie Chen

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/802/

zbMATH Keywords

complexityconstraint satisfactiondecision diagramssuccinct representations

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

Tractability in constraint satisfaction problems: a survey ⋮ Structural decompositions for problems with global constraints ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ The power of propagation: when GAC is enough ⋮ On the complexity of existential positive queries ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• A unified theory of structural tractability for constraint satisfaction problems
• Tree clustering for constraint networks
• Constraints, consistency and closure
• A comparison of structural CSP decomposition methods
• Query evaluation via tree-decompositions
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• 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
• Theory and Applications of Satisfiability Testing
• Tractable Structures for Constraint Satisfaction with Truth Tables
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Constraint satisfaction with succinctly specified relations