9 citations · 47 across the 26 of their papers we have counts for
40 papers
Temporal Graph Realization With Bounded Stretch
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first time steps, and then it reappears recurrently every time s…
Realizing temporal transportation trees
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
In this paper, we study the complexity of the periodic temporal graph realization problem with respect to upper bounds on the fastest path durations among its vertices. This constr…
Realizing temporal graphs from fastest travel times
Nina Klobas, George B. Mertzios, Hendrik Molter +1
In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal gra…
In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
Pascal Kunz, Hendrik Molter, Meirav Zehavi
A temporal graph has an edge set that may change over discrete time steps, and a temporal path (or walk) must traverse edges that appear at increasing time steps. Accordingly, two…
Hardness of Interval Scheduling on Unrelated Machines
Danny Hermelin, Yuval Itzhaki, Hendrik Molter +1
We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lea…
Counting Temporal Paths
Jessica Enright, Kitty Meeks, Hendrik Molter
The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness ce…
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions
Danny Hermelin, Hendrik Molter, Dvir Shabtay
The problem asks to determine -- given jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any s…
The complexity of computing optimum labelings for temporal connectivity
Nina Klobas, George B. Mertzios, Hendrik Molter +1
A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex to every other vertex . In…
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…
Fairness in Repetitive Scheduling
Danny Hermelin, Hendrik Molter, Rolf Niedermeier +2
Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customer…
Temporal Interval Cliques and Independent Sets
Danny Hermelin, Yuval Itzhaki, Hendrik Molter +1
Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. The Temporal Clique problem, that generalizes th…
The Complexity of Finding Temporal Separators under Waiting Time Constraints
Hendrik Molter
In this work, we investigate the computational complexity of Restless Temporal -Separation, where we are asked whether it is possible to destroy all restless temporal paths…
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
Maciej Rymar, Hendrik Molter, André Nichterlein +1
In static graphs, the betweenness centrality of a graph vertex measures how many times this vertex is part of a shortest path between any two graph vertices. Betweenness centrality…
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…
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, George B. Mertzios, Hendrik Molter +2
We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal pa…
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…
Equitable Scheduling on a Single Machine
Klaus Heeger, Danny Hermelin, George B. Mertzios +3
We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalizati…
Algorithmic Aspects of Temporal Betweenness
Sebastian Buß, Hendrik Molter, Rolf Niedermeier +1
The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world gra…
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…
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…
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter +1
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, grap…