6 citations · 8 across the 3 of their papers we have counts for
3 papers
math.CO2017★ 1 cited
On the complexity of generalized chromatic polynomials
A. Goodall, M. Hermann, T. Kotek +2
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for h…
cs.CC2015★ 6 cited
Minimal Distance of Propositional Models
Mike Behrisch, Miki Hermann, Stefan Mengel +1
We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find…
cs.CC2010★ 1 cited
Complexity of Existential Positive First-Order Logic
Manuel Bodirsky, Miki Hermann, Florian Richoux
Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logs…