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 (3)

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

This page was built for publication: On Planar Boolean CSP