On Planar Boolean CSP
From MaRDI portal
Recommendations
- On planar valued CSPs
- On Planar Valued CSPs
- On the complexity of planar Boolean circuits
- Even delta-matroids and the complexity of planar Boolean CSPs
- Even delta-matroids and the complexity of planar Boolean CSPs
- On the planar monotone computation of Boolean functions
- On the CSP Dichotomy Conjecture
- An approximation trichotomy for Boolean \#CSP
Cites work
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Classifying the Complexity of Constraints Using Finite Algebras
- Constraint Satisfaction Problems of Bounded Width
- Fanout limitations on constraint systems
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- scientific article; zbMATH DE number 4094812 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2003
- Minimum-weight triangulation is NP-hard
- Paths, Trees, and Flowers
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The linear delta-matroid parity problem
Cited in
(7)- On planar valued CSPs
- On Planar Valued CSPs
- Hybrid tractable classes of constraint problems
- On the Complexity of Holant Problems
- Planar 3-SAT with a clause/variable cycle
- A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
- Faster algorithms on linear delta-matroids
This page was built for publication: On Planar Boolean CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448805)
