Constraint satisfaction with bounded treewidth revisited
From MaRDI portal
Publication:847262
DOI10.1016/j.jcss.2009.04.003zbMath1186.68443MaRDI 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
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
On the complexity of some colorful problems parameterized by treewidth, On the power of structural decompositions of graph-based representations of constraint problems
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