19 citations · 75 across the 31 of their papers we have counts for
7 papers · 1 filter
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…
All Paths Lead to Rome
Kevin Goergen, Henning Fernau, Esther Oest +1
All roads lead to Rome is the core idea of the puzzle game Roma. It is played on an grid consisting of quadratic cells. Those cells are grouped into boxes of at most f…
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady, Mark de Berg, Karl Bringmann +6
We consider the unlabeled motion-planning problem of unit-disc robots moving in a simple polygonal workspace of edges. The goal is to find a motion plan that moves the robo…
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…