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)
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Unnamed Item, A Dichotomy for First-Order Reducts of Unary Structures, Unnamed Item, Unnamed Item, Solving CSPs Using Weak Local Consistency, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Complexity and polymorphisms for digraph constraint problems under some basic constructions, Unnamed Item, Equivariant algorithms for constraint satisfaction problems over coset templates, List-homomorphism problems on graphs and arc consistency, An algebraic hardness criterion for surjective constraint satisfaction., Rigid binary relations on a 4-element domain, Quantified constraint satisfaction and the polynomially generated powers property, Maltsev digraphs have a majority polymorphism, The complexity of the list homomorphism problem for graphs, A new line of attack on the dichotomy conjecture, CSP duality and trees of bounded pathwidth, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Generic expression hardness results for primitive positive formula comparison, Characterizations of several Maltsev conditions., Commutative idempotent groupoids and the constraint satisfaction problem., Decidability of absorption in relational structures of bounded width., CSP for binary conservative relational structures, Robustly Solvable Constraint Satisfaction Problems, On the CSP Dichotomy Conjecture, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Constraint Satisfaction Problems Solvable by Local Consistency Methods, On Planar Boolean CSP