research
∙
06/26/2023
Algorithmics of Egalitarian versus Equitable Sequences of Committees
We study the election of sequences of committees, where in each of τ lev...
share
research
∙
01/28/2022
Placing Green Bridges Optimally, with Habitats Inducing Cycles
Choosing the placement of wildlife crossings (i.e., green bridges) to re...
research
∙
11/17/2021
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring
We consider the algorithmic complexity of recognizing bipartite temporal...
research
∙
10/07/2021
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
A polynomial Turing kernel for some parameterized problem P is a polynom...
research
∙
07/09/2021
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Proximity graphs have been studied for several decades, motivated by app...
research
∙
04/17/2021
3-Coloring on Regular, Planar, and Ordered Hamiltonian Graphs
We prove that 3-Coloring remains NP-hard on 4- and 5-regular planar Hami...
research
∙
04/12/2021
Feedback Vertex Set on Hamiltonian Graphs
We study the computational complexity of Feedback Vertex Set on subclass...
research
∙
02/08/2021
Placing Green Bridges Optimally, with a Multivariate Analysis
We study the problem of placing wildlife crossings, such as green bridge...
research
∙
11/04/2020
A Multistage View on 2-Satisfiability
We study q-SAT in the multistage model, focusing on the linear-time solv...
research
∙
05/05/2020
Multistage Committee Election
Electing a single committee of a small size is a classical and well-unde...
research
∙
04/28/2020
As Time Goes By: Reflections on Treewidth for Temporal Graphs
Treewidth is arguably the most important structural graph parameter lead...
research
∙
02/18/2020
Multistage s-t Path: Confronting Similarity with Dissimilarity
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, compr...
research
∙
06/03/2019
Multistage Vertex Cover
Covering all edges of a graph by a minimum number of vertices, this is t...
research
∙
12/25/2018
On (1+ε)-approximate problem kernels for the Rural Postman Problem
Given a graph G=(V,E) with edge weights ω E→ N∪{0} and a subset R⊆ E of ...
research
∙
08/07/2018
On the Computational Complexity of Length- and Neighborhood-Constrained Path Problems
Finding paths in graphs is a fundamental graph-theoretic task. In this w...
research
∙
06/25/2018
Parameterized algorithms and data reduction for the short secluded s-t-path problem
Given a graph G=(V,E), two vertices s,t∈ V, and two integers k,ℓ, we sea...
research
∙
06/25/2018
Parameterized algorithms and data reduction for safe convoy routing
We study a problem that models safely routing a convoy through a transpo...
research
∙
04/24/2018
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
We study the NP-hard Shortest Path Most Vital Edges problem arising in t...
research
∙
03/01/2018
Temporal Graph Classes: A View Through Temporal Separators
We investigate the computational complexity of separating two distinct v...
research
∙
11/13/2017
Fair Knapsack
We study the following multiagent variant of the knapsack problem. We ar...
research
∙
11/02/2017
On Efficiently Finding Small Separators in Temporal Graphs
Vertex separators, that is, vertex sets whose deletion disconnects two d...
research
∙
11/02/2017
The Computational Complexity of Finding Separators in Temporal Graphs
Vertex separators, that is, vertex sets whose deletion disconnects two d...
research
∙
10/20/2017