On Planar Boolean CSP
From MaRDI portal
Publication:3448805
DOI10.1007/978-3-662-47672-7_35zbMath1410.68163OpenAlexW2403828268MaRDI QIDQ3448805
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_35
Related Items
On planar valued CSPs, Hybrid Tractable Classes of Constraint Problems, On the Complexity of Holant Problems
Cites Work
- Unnamed Item
- The linear delta-matroid parity problem
- The complexity of planar Boolean \#CSP with complex weights
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Minimum-weight triangulation is NP-hard
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Constraint Satisfaction Problems of Bounded Width
- Classifying the Complexity of Constraints Using Finite Algebras
- Paths, Trees, and Flowers
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2003
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Fanout limitations on constraint systems