4 citations · 9 across the 18 of their papers we have counts for
19 papers
Lettericity Is NP-Complete
Henning Fernau, Samuel German, Kevin Mann +1
The lettericity of a graph is the smallest size of a set such that there exist and a so-called decoder for which is is…
Parameterized Enumeration of Minimal Defensive Alliances
Henning Fernau, Kevin Mann, Arne Meier +1
In this paper, we consider the complexity of enumerating inclusion minimal defensive alliances. We present a polynomial-delay algorithm on graphs with maximum degree 5. We compleme…
Language-Representability: Possibilities and Limitations
Zhidan Feng, Henning Fernau, Pamela Fleischmann +2
The study of word-representability was initiated by the seminal work of Kitaev and Pyatkin in 2008 that has later led to the monograph by Kitaev and Lozin in 2015. In this paper, w…
On Languages Describing Large Graph Classes
Henning Fernau, Pamela Fleischmann, Kevin Mann +1
In this work, we introduce a new notion for representing graph classes with formal languages. In contrast to the seminal work by Kitaev and Pyatkin to represent graphs by words, we…
Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
Jean Cardinal, Kevin Mann, Akira Suzuki +3
We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two ind…
Enumeration With Nice Roman Domination Properties
Kevin Mann
Although Extension Perfect Roman Domination is NP-complete, all minimal (with respect to the pointwise order) perfect Roman dominating functions can be enumerated with polynomial d…
How to Reconfigure Your Alliances
Henning Fernau, Kevin Mann
Different variations of alliances in graphs have been introduced into the graph-theoretic literature about twenty years ago. More broadly speaking, they can be interpreted as group…
On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
Kazuhiro Kurita, Kevin Mann
In this paper, we address the enumeration of (induced) - paths and minimal - separators. These problems are some of the most famous classical enumeration problems that…
Generalized Word-Representable Graphs
Zhidan Feng, Henning Fernau, Pamela Fleischmann +2
The literature on word-representable graphs is quite rich, and a number of variations of the original definition have been proposed over the years. We are initiating a systematic s…
Offensive Alliances in Signed Graphs
Zhidan Feng, Henning Fernau, Kevin Mann +1
Signed graphs have been introduced to enrich graph structures expressing relationships between persons or general social entities, introducing edge signs to reflect the nature of t…
Enumerating Minimal Defensive Alliances
Zhidan Feng, Henning Fernau, Kevin Mann
In this paper, we study the task of enumerating (and counting) locally and globally minimal defensive alliances in graphs. We consider general graphs as well as special graph class…
Perfect Roman Domination and Unique Response Roman Domination
Henning Fernau, Kevin Mann
The idea of enumeration algorithms with polynomial delay is to polynomially bound the running time between any two subsequent solutions output by the enumeration algorithm. While i…
Defensive Alliances in Signed Networks
Emmanuel Arrighi, Zhidan Feng, Henning Fernau +3
The analysis of (social) networks and multi-agent systems is a central theme in Artificial Intelligence. Some line of research deals with finding groups of agents that could work t…
Hitting the Romans
Henning Fernau, Kevin Mann
Roman domination is one of few examples where the related extension problem is polynomial-time solvable even if the original decision problem is NP-complete. This is interesting, a…
Parameterizing Path Partitions
Henning Fernau, Florent Foucaud, Kevin Mann +2
We study the algorithmic complexity of partitioning the vertex set of a given (di)graph into a small number of paths. The Path Partition problem (PP) has been studied extensively,…
Recognizing well-dominated graphs is coNP-complete
Akanksha Agrawal, Henning Fernau, Philipp Kindermann +2
A graph is well-covered if every minimal vertex cover of is minimum, and a graph is well-dominated if every minimal dominating set of is minimum. Studies on well-co…
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Faisal N. Abu-Khzam, Henning Fernau, Kevin Mann
The concept of Roman domination has recently been studied concerning enumerating and counting (WG 2022). It has been shown that minimal Roman dominating functions can be enumerated…
Enumerating Connected Dominating Sets
Faisal Abu-Khzam, Henning Fernau, Benjamin Gras +2
The question to enumerate all inclusion-minimal connected dominating sets in a graph of order in time significantly less than is an open question that was asked in many p…
Minimal Roman Dominating Functions: Extensions and Enumeration
Faisal N. Abu-Khzam, Henning Fernau, Kevin Mann
Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves di…