Closure functions and width 1 problems

DOI10.1007/978-3-540-48085-3_12MaRDI QIDQ4495111zbMATH OpenFDO

Authors Víctor Dalmau, Justin Pearson

Publication date 10 August 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-48085-3_12

zbMATH Keywords

constraint satisfaction problemslocal consistency

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Recommendations

• Constraints, consistency and closure
• scientific article; zbMATH DE number 1942453
• Closure properties of constraints
• Solving CSPs using weak local consistency

Cited in

(37)

• Existentially restricted quantified constraint satisfaction
• Relatively quantified constraint satisfaction
• Peek arc consistency
• The power of propagation: when GAC is enough
• A new tractable class of constraint satisfaction problems
• Constraint satisfaction with succinctly specified relations
• Tractable combinations of theories via sampling
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Semilattice polymorphisms and chordal graphs
• Retractions onto series-parallel posets
• Tractability in constraint satisfaction problems: a survey
• On algebras with many symmetric operations
• On the CSP Dichotomy Conjecture
• CSP dichotomy for special triads
• List-homomorphism problems on graphs and arc consistency
• scientific article; zbMATH DE number 1942453 (Why is no real title available?)
• Reflexive digraphs with near unanimity polymorphisms
• Weak consistency notions for all the CSPs of bounded width
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• Quantified Constraints in Twenty Seventeen
• Solving CSPs using weak local consistency
• The power of linear programming for general-valued CSPs
• Dualities for Constraint Satisfaction Problems
• A Logical Approach to Constraint Satisfaction
• CLAP: A New Algorithm for Promise CSPs
• The smallest hard trees
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Symmetric linear arc monadic Datalog and gadget reductions
• Smooth approximations and relational width collapses
• Symmetric linear arc monadic Datalog and gadget reductions
• Satisfiability of commutative vs. non-commutative CSPs
• Periodic constraint satisfaction problems: Tractable subclasses
• H-coloring dichotomy revisited
• A new line of attack on the dichotomy conjecture
• There are no pure relational width 2 constraint satisfaction problems

This page was built for publication: Closure functions and width 1 problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4495111)