1 citations · 2 across the 5 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016
On planar variants of the monotone satisfiability problem with bounded variable appearances
Andreas Darmann, Janosch Döcker, Britta Dorn
We show NP-completeness for several planar variants of the monotone satisfiability problem with bounded variable appearances. With one exception the presented variants have an asso…
cs.CC2016
Monotone 3-Sat-4 is NP-complete
Andreas Darmann, Janosch Döcker
Monotone 3-Sat-4 is a variant of the satisfiability problem for boolean formulae in conjunctive normal form. In this variant, each clause contains exactly three literals---either a…