research
∙
04/06/2022
Disentangling the Computational Complexity of Network Untangling
We study the network untangling problem introduced by Rozenshtein, Tatti...
share
research
∙
03/29/2022
Restless Temporal Path Parameterized Above Lower Bounds
Reachability questions are one of the most fundamental algorithmic primi...
research
∙
05/18/2021
Interference-free Walks in Time: Temporally Disjoint Paths
We investigate the computational complexity of finding temporally disjoi...
research
∙
05/14/2021
Optimal Virtual Network Embeddings for Tree Topologies
The performance of distributed and data-centric applications often criti...
research
∙
05/11/2021
Parameterized Algorithms for Diverse Multistage Problems
The world is rarely static – many problems need not only be solved once ...
research
∙
02/22/2021
Temporal Reachability Minimization: Delaying vs. Deleting
We study spreading processes in temporal graphs, i. e., graphs whose con...
research
∙
02/12/2021
The Complexity of Transitively Orienting Temporal Graphs
In a temporal network with discrete time-labels on its edges, entities a...
research
∙
10/20/2020
A Faster Parameterized Algorithm for Temporal Matching
A temporal graph is a sequence of graphs (called layers) over the same v...
research
∙
07/24/2020
Using a geometric lens to find k disjoint shortest paths
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1...
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
∙
09/13/2019
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Computing a (shortest) path between two vertices in a graph is one of th...
research
∙
06/03/2019
Multistage Vertex Cover
Covering all edges of a graph by a minimum number of vertices, this is t...
research
∙
05/13/2019
Computing Maximum Matchings in Temporal Graphs
We study the computational complexity of finding maximum-cardinality tem...
research
∙
06/29/2018
Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
We consider a variant of the matroid median problem introduced by Krishn...
research
∙
06/29/2018
Fixed-parameter algorithms for facility location under matroid constraints
We introduce a new uncapacitated discrete facility location problem, whe...
research
∙
06/29/2018
Facility location under matroid constraints: fixed-parameter algorithms and applications
We study an NP-hard uncapacitated discrete facility location problem: Th...
research
∙
06/25/2018
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
Finding a maximum-cardinality or maximum-weight matching in (edge-weight...
research
∙
03/01/2018
Temporal Graph Classes: A View Through Temporal Separators
We investigate the computational complexity of separating two distinct v...
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