Constraint Satisfaction Problems of Bounded Width
From MaRDI portal
Publication:5171200
DOI10.1109/FOCS.2009.32zbMath1292.68088MaRDI QIDQ5171200
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (31)
On Planar Boolean CSP ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ CSP for binary conservative relational structures ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Equivariant algorithms for constraint satisfaction problems over coset templates ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ List-homomorphism problems on graphs and arc consistency ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ A new line of attack on the dichotomy conjecture ⋮ Maltsev digraphs have a majority polymorphism ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Unnamed Item ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ On the CSP Dichotomy Conjecture ⋮ Rigid binary relations on a 4-element domain ⋮ The complexity of the list homomorphism problem for graphs ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ CSP duality and trees of bounded pathwidth ⋮ Decidability of absorption in relational structures of bounded width. ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Characterizations of several Maltsev conditions. ⋮ Commutative idempotent groupoids and the constraint satisfaction problem.
This page was built for publication: Constraint Satisfaction Problems of Bounded Width
