1 citations · 1 across the 1 of their papers we have counts for
3 papers
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…
cs.DM2015★ 1 cited
On the shortest path game: extended version
Andreas Darmann, Ulrich Pferschy, Joachim Schauer
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting…