A comparison of structural CSP decomposition methods
From MaRDI portal
Publication:1589639
DOI10.1016/S0004-3702(00)00078-3zbMath0952.68044WikidataQ29307483 ScholiaQ29307483MaRDI QIDQ1589639
Nicola Leone, Georg Gottlob, Francesco Scarcello
Publication date: 12 December 2000
Published in: Artificial Intelligence (Search for Journal in Brave)
treewidthhypergraphsdecomposition methodsconstraint satisfactionhypertree widthbiconnected componentstractable casescycle cutsetsdegree of cyclicitytree-clustering
Related Items (52)
Disjunctions, independence, refinements ⋮ Structural tractability of counting of solutions to conjunctive queries ⋮ Structural decompositions for problems with global constraints ⋮ On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ On minimal constraint networks ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Tractable counting of the answers to conjunctive queries ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Equivalence between hypergraph convexities ⋮ Generic local computation ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ Computing partial hypergraphs of bounded width ⋮ CSP beyond tractable constraint languages ⋮ The power of propagation: when GAC is enough ⋮ Combining restarts, nogoods and bag-connected decompositions for solving csps ⋮ Dynamic Management of Heuristics for Solving Structured CSPs ⋮ Constraint satisfaction with succinctly specified relations ⋮ On Sparse Discretization for Graphical Games ⋮ A unified theory of structural tractability for constraint satisfaction problems ⋮ The complexity of reasoning with global constraints ⋮ Unifying tree decompositions for reasoning in graphical models ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Task-dependent qualitative domain abstraction ⋮ Coalition formation in social environments with logic-based agents1 ⋮ Hypertree width and related hypergraph invariants ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Treewidth computations. I: Upper bounds ⋮ Hypertree decompositions and tractable queries ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ The complexity of counting homomorphisms seen from the other side ⋮ Diagnosing tree-structured systems ⋮ Causal graphs and structurally restricted planning ⋮ A polynomial relational class of binary CSP ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results ⋮ Learning to Integrate Deduction and Search in Reasoning about Quantified Boolean Formulas ⋮ Fast and parallel decomposition of constraint satisfaction problems ⋮ A Logical Approach to Constraint Satisfaction ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Structural tractability of enumerating CSP solutions ⋮ Large hypertree width for sparse random hypergraphs ⋮ Fixed-parameter complexity in AI and nonmonotonic reasoning ⋮ Lifted Reasoning for Combinatorial Counting ⋮ Hybrid backtracking bounded by tree-decomposition of constraint networks
Cites Work
- Hypertree decompositions and tractable queries
- Network-based heuristics for constraint-satisfaction problems
- Constraint satisfaction from a deductive viewpoint
- Tree clustering for constraint networks
- Decomposing constraint satisfaction problems using database techniques
- Conjunctive query containment revisited
- Conjunctive-query containment and constraint satisfaction
- On the Desirability of Acyclic Database Schemes
- Syntactic Characterization of Tree Database Schemas
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- A sufficient condition for backtrack-bounded search
- Power of Natural Semijoins
- A Sufficient Condition for Backtrack-Free Search
- Closure properties of constraints
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A comparison of structural CSP decomposition methods
