Constraint satisfaction with bounded treewidth revisited
From MaRDI portal
Publication:847262
DOI10.1016/J.JCSS.2009.04.003zbMATH Open1186.68443OpenAlexW1983648207MaRDI QIDQ847262FDOQ847262
Publication date: 12 February 2010
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.04.003
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Some simplified NP-complete graph problems
- Conjunctive-query containment and constraint satisfaction
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Constraint solving via fractional edge covers
- Hypertree decompositions and tractable queries
- Theory and Applications of Satisfiability Testing
- Tree clustering for constraint networks
- A sufficient condition for backtrack-bounded search
- On the complexity of database queries
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Constraint Satisfaction with Bounded Treewidth Revisited
- Algorithms for Propositional Model Counting
- Graph-Theoretic Concepts in Computer Science
Cited In (25)
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Grundy Distinguishes Treewidth from Pathwidth
- Tractability in constraint satisfaction problems: a survey
- SAT backdoors: depth beats size
- Algorithmic Applications of Tree-Cut Width
- Complexity and approximability of parameterized MAX-CSPs
- Title not available (Why is that?)
- Backdoors into heterogeneous classes of SAT and CSP
- Slim tree-cut width
- New width parameters for SAT and \#SAT
- Solving infinite-domain CSPs using the patchwork property
- Title not available (Why is that?)
- Myhill-Nerode Methods for Hypergraphs
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Algorithmic Applications of Tree-Cut Width
- Answer set solving with bounded treewidth revisited
- Structural parameters for scheduling with assignment restrictions
- Parametrised Complexity of Satisfiability in Temporal Logic
- On the complexity of some colorful problems parameterized by treewidth
- On the parameterized complexity of freezing dynamics
- On the power of structural decompositions of graph-based representations of constraint problems
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- On the impact of treewidth in the computational complexity of freezing dynamics
- Does Treewidth Help in Modal Satisfiability?
Recommendations
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination 👍 👎
- Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics 👍 👎
- Bounded Tree-Width and CSP-Related Problems 👍 👎
- Constraint Satisfaction with Bounded Treewidth Revisited 👍 👎
- Extended formulation for CSP that is compact for instances of bounded treewidth 👍 👎
- The Polytope of Tree-Structured Binary Constraint Satisfaction Problems 👍 👎
- The complexity of constraint satisfaction revisited 👍 👎
- Answer set solving with bounded treewidth revisited 👍 👎
- Tree Dualities for Constraint Satisfaction 👍 👎
This page was built for publication: Constraint satisfaction with bounded treewidth revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847262)
