Constraint satisfaction with bounded treewidth revisited
From MaRDI portal
Publication:847262
DOI10.1016/j.jcss.2009.04.003zbMath1186.68443OpenAlexW1983648207MaRDI QIDQ847262
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
Related Items (20)
Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ SAT backdoors: depth beats size ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Unnamed Item ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ New width parameters for SAT and \#SAT ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Unnamed Item ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ On the impact of treewidth in the computational complexity of freezing dynamics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hypertree decompositions and tractable queries
- Tree clustering for constraint networks
- Some simplified NP-complete graph problems
- A partial k-arboretum of graphs with bounded treewidth
- On the complexity of database queries
- Conjunctive-query containment and constraint satisfaction
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Algorithms for Propositional Model Counting
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Constraint Satisfaction with Bounded Treewidth Revisited
- Constraint solving via fractional edge covers
- A sufficient condition for backtrack-bounded search
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Theory and Applications of Satisfiability Testing
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Constraint satisfaction with bounded treewidth revisited
