8 citations · 35 across the 16 of their papers we have counts for
21 papers
Smooth Routing in Decaying Trees
Till Fluschnik, Amela Pucic, Malte Renken
Motivated by evacuation scenarios arising in extreme events such as flooding or forest fires, we study the problem of smoothly scheduling a set of paths in graphs where connections…
Locally Rainbow Paths
Till Fluschnik, Leon Kellerhals, Malte Renken
We introduce the algorithmic problem of finding a locally rainbow path of length connecting two distinguished vertices and in a vertex-colored directed graph. Herein…
Terrain-like Graphs and the Median Genocchi Numbers
Vincent Froese, Malte Renken
A graph with vertex set is terrain-like if, for any edge pair with , the edge also exists. Terrain-like graphs frequently appe…
Giant Components in Random Temporal Graphs
Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi +4
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi…
Delay-Robust Routes in Temporal Graphs
Eugen Füchsle, Hendrik Molter, Rolf Niedermeier +1
Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodi…
Temporal Connectivity: Coping with Foreseen and Unforeseen Delays
Eugen Füchsle, Hendrik Molter, Rolf Niedermeier +1
Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficul…
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Pascal Kunz, Till Fluschnik, Rolf Niedermeier +1
Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computation…
On Finding Separators in Temporal Split and Permutation Graphs
Nicolas Maack, Hendrik Molter, Rolf Niedermeier +1
Removing all connections between two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s,z)-separatio…
Parameterized Algorithms for Diverse Multistage Problems
Leon Kellerhals, Malte Renken, Philipp Zschoche
The world is rarely static -- many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the "multistage" view on computatio…
Two Influence Maximization Games on Graphs Made Temporal
Niclas Boehmer, Vincent Froese, Julia Henkel +3
To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi games from static to temporal graphs, where edges may appear or disappea…
Temporal Reachability Minimization: Delaying vs. Deleting
Hendrik Molter, Malte Renken, Philipp Zschoche
We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases…
The Complexity of Transitively Orienting Temporal Graphs
George B. Mertzios, Hendrik Molter, Malte Renken +2
In a temporal network with discrete time-labels on its edges, entities and information can only ``flow'' along sequences of edges whose time-labels are non-decreasing (resp. increa…
Sharp Thresholds in Random Simple Temporal Graphs
Arnaud Casteigts, Michael Raskin, Malte Renken +1
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is c…
Using a geometric lens to find k disjoint shortest paths
Matthias Bentert, André Nichterlein, Malte Renken +1
Given an undirected -vertex graph and pairs of terminal vertices , the -Disjoint Shortest Paths (-DSP)-problem asks whether there are …
As Time Goes By: Reflections on Treewidth for Temporal Graphs
Till Fluschnik, Hendrik Molter, Rolf Niedermeier +2
Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal…
Feedback Edge Sets in Temporal Graphs
Roman Haag, Hendrik Molter, Rolf Niedermeier +1
The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provid…
Multistage Graph Problems on a Global Budget
Klaus Heeger, Anne-Sophie Himmel, Frank Kammer +3
Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks. In this context, the multistage view on computational problems is amo…
Persistent Graphs and Cyclic Polytope Triangulations
Vincent Froese, Malte Renken
We prove a bijection between the triangulations of the 3-dimensional cyclic polytope C(n+2, 3) and persistent graphs with n vertices. We show that under this bijection the Stasheff…
Enumerating Isolated Cliques in Temporal Networks
Hendrik Molter, Rolf Niedermeier, Malte Renken
Isolation is a concept from the world of clique enumeration that is mostly used to model communities that do not have much contact to the outside world. Herein, a clique is conside…
Advancing Through Terrains
Vincent Froese, Malte Renken
We study terrain visibility graphs, a well-known graph class closely related to polygon visibility graphs in computational geometry, for which a precise graph-theoretical character…
Comparing Temporal Graphs Using Dynamic Time Warping
Vincent Froese, Brijnesh Jain, Rolf Niedermeier +1
Within many real-world networks the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal…