On Planar Boolean CSP

DOI10.1007/978-3-662-47672-7_35zbMath1410.68163OpenAlexW2403828268MaRDI QIDQ3448805

Zdeněk Dvořák, Martin Kupec

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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