6 papers
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…
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…
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…
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,…