Constraint Satisfaction with Bounded Treewidth Revisited

DOI10.1007/11889205_36MaRDI QIDQ3524254zbMATH OpenOpenAlexFDO

Authors Marko Samer, Stefan Szeider

Publication date 9 September 2008

Published in Principles and Practice of Constraint Programming - CP 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11889205_36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Dynamic programming (90C39)

Recommendations

• Constraint satisfaction with bounded treewidth revisited
• Can you beat treewidth?
• Parameterized complexity of constraint satisfaction problems
• Combining treewidth and backdoors for CSP
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms

Cited in

(20)

• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Algorithms for propositional model counting
• Answer set solving with bounded treewidth revisited
• Can you beat treewidth?
• Algorithms for Propositional Model Counting
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Tradeoffs in the Complexity of Backdoor Detection
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• Parametrised complexity of satisfiability in temporal logic
• Does Treewidth Help in Modal Satisfiability?
• Bounded backtracking for the valued constraint satisfaction problems
• Does treewidth help in modal satisfiability? (Extended abstract)
• On the expressive power of CNF formulas of bounded tree- and clique-width
• Learning cluster-based structure to solve constraint satisfaction problems
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
• Parameterized complexity of constraint satisfaction problems
• Constraint satisfaction with bounded treewidth revisited
• Tensor network contractions for \#SAT
• Extended formulation for CSP that is compact for instances of bounded treewidth

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 Q3524254)