research
∙
10/28/2022
Terrain-like Graphs and the Median Genocchi Numbers
A graph with vertex set {1,…,n} is terrain-like if, for any edge pair {a...
share
research
∙
05/30/2022
Giant Components in Random Temporal Graphs
A temporal graph is a graph whose edges appear only at certain points in...
research
∙
01/14/2022
Delay-Robust Routes in Temporal Graphs
Most transportation networks are inherently temporal: Connections (e.g. ...
research
∙
01/13/2022
Temporal Connectivity: Coping with Foreseen and Unforeseen Delays
Consider planning a trip in a train network. In contrast to, say, a road...
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
∙
05/25/2021
On Finding Separators in Temporal Split and Permutation Graphs
Removing all connections between two vertices s and z in a graph by remo...
research
∙
05/12/2021
Two Influence Maximization Games on Graphs Made Temporal
To address the dynamic nature of real-world networks, we generalize comp...
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
∙
11/07/2020
Sharp Thresholds in Random Simple Temporal Graphs
A graph whose edges only appear at certain points in time is called a te...
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
∙
03/30/2020
Feedback Edge Sets in Temporal Graphs
The classical, linear-time solvable Feedback Edge Set problem is concern...
research
∙
12/09/2019
Multistage Graph Problems on a Global Budget
Time-evolving or temporal graphs gain more and more popularity when stud...
research
∙
12/09/2019
Multistage Problems on a Global Budget
Time-evolving or temporal graphs gain more and more popularity when stud...
research
∙
11/12/2019
Terrain Visibility Graphs and Cyclic Polytope Triangulations
We prove a bijection between the triangulations of the 3-dimensional cyc...
research
∙
09/13/2019
Enumerating Isolated Cliques in Temporal Networks
Isolation has been shown to be a valuable concept in the world of clique...
research
∙
04/18/2019
Advancing Through Terrains
We study terrain visibility graphs, a well-known graph class closely rel...
research
∙
10/15/2018