A unified theory of structural tractability for constraint satisfaction problems
From MaRDI portal
Publication:931717
DOI10.1016/j.jcss.2007.08.001zbMath1151.68640MaRDI QIDQ931717
Marc Gyssens, Peter G. Jeavons, David A. Cohen
Publication date: 26 June 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://ora.ox.ac.uk/objects/uuid:de8a7f23-2c05-4495-9205-8559837873db
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Uniform Constraint Satisfaction Problems and Database Theory, A unified theory of structural tractability for constraint satisfaction problems, On the power of structural decompositions of graph-based representations of constraint problems, Approximability of clausal constraints, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Solving nonograms by combining relaxations, Constraint satisfaction with succinctly specified relations, Algorithms for propositional model counting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hypertree decompositions and tractable queries
- A unified theory of structural tractability for constraint satisfaction problems
- Network-based heuristics for constraint-satisfaction problems
- Tree clustering for constraint networks
- Consistency in networks of relations
- Decomposing constraint satisfaction problems using database techniques
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Conjunctive query containment revisited
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- On the Desirability of Acyclic Database Schemes
- Marshals, monotone marshals, and hypertree-width
- A sufficient condition for backtrack-bounded search