A unified theory of structural tractability for constraint satisfaction problems
From MaRDI portal
Publication:931717
DOI10.1016/j.jcss.2007.08.001zbMath1151.68640OpenAlexW2153629319MaRDI 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
Related Items (21)
Structural tractability of counting of solutions to conjunctive queries ⋮ Structural decompositions for problems with global constraints ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Modularity-based decompositions for valued CSP ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ The power of propagation: when GAC is enough ⋮ Constraint satisfaction with succinctly specified relations ⋮ A unified theory of structural tractability for constraint satisfaction problems ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ Approximability of clausal constraints ⋮ Algorithms for propositional model counting ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Solving nonograms by combining relaxations ⋮ Fast and parallel decomposition of constraint satisfaction problems ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Structural tractability of enumerating CSP solutions
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
This page was built for publication: A unified theory of structural tractability for constraint satisfaction problems
