Constraint satisfaction with bounded treewidth revisited

DOI10.1016/j.jcss.2009.04.003zbMath1186.68443MaRDI QIDQ847262

Stefan Szeider, Marko Samer

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

zbMATH Keywords

treewidth; constraint satisfaction; parameterized complexity

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Parametrised Complexity of Satisfiability in Temporal Logic, Tractability in constraint satisfaction problems: a survey, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, On the complexity of some colorful problems parameterized by treewidth, Backdoors into heterogeneous classes of SAT and CSP, On the power of structural decompositions of graph-based representations of constraint problems, Structural parameters for scheduling with assignment restrictions, Complexity and approximability of parameterized MAX-CSPs, Myhill-Nerode Methods for Hypergraphs, Algorithmic Applications of Tree-Cut Width

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