research
∙
09/13/2023
Perfect Roman Domination and Unique Response Roman Domination
The idea of enumeration algorithms with polynomial delay is to polynomia...
share
research
∙
09/13/2023
Defensive Alliances in Signed Networks
The analysis of (social) networks and multi-agent systems is a central t...
research
∙
02/22/2023
Hitting the Romans
Roman domination is one of few examples where the related extension prob...
research
∙
01/05/2023
Sum Labelling Graphs of Maximum Degree Two
The concept of sum labelling was introduced in 1990 by Harary. A graph i...
research
∙
12/22/2022
Parameterizing Path Partitions
We study the algorithmic complexity of partitioning the vertex set of a ...
research
∙
08/18/2022
Recognizing well-dominated graphs is coNP-complete
A graph G is well-covered if every minimal vertex cover of G is minimum,...
research
∙
08/10/2022
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
The concept of Roman domination has recently been studied concerning enu...
research
∙
07/19/2022
All Paths Lead to Rome
All roads lead to Rome is the core idea of the puzzle game Roma. It is p...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
research
∙
04/29/2022
Enumerating Connected Dominating Sets
The question to enumerate all inclusion-minimal connected dominating set...
research
∙
04/10/2022
Minimal Roman Dominating Functions: Extensions and Enumeration
Roman domination is one of the many variants of domination that keeps mo...
research
∙
08/11/2021
Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited
The problem DFA-Intersection-Nonemptiness asks if a given number of dete...
research
∙
07/27/2021
The Space Complexity of Sum Labelling
A graph is called a sum graph if its vertices can be labelled by distinc...
research
∙
05/19/2021
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
In its most traditional setting, the main concern of optimization theory...
research
∙
05/04/2020
Synchronizing Deterministic Push-Down Automata Can Be Really Hard
The question if a deterministic finite automaton admits a software reset...
research
∙
05/04/2020
Synchronization of Deterministic Visibly Push-Down Automata
We generalize the concept of synchronizing words for finite automata, wh...
research
∙
03/12/2020
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
The Int_reg-problem of a combinatorial problem P asks, given a nondeterm...
research
∙
10/10/2018
Extension of vertex cover and independent set in some classes of graphs and generalizations
We consider extension variants of the classical graph problems Vertex Co...
research
∙
10/10/2018
On the Complexity of Solution Extension of Optimization Problems
The question if a given partial solution to a problem can be extended re...
research
∙
06/19/2017