research
∙
09/18/2023
How to Make Knockout Tournaments More Popular?
Given a mapping from a set of players to the leaves of a complete binary...
share
research
∙
02/17/2023
Realizing temporal graphs from fastest travel times
In this paper we initiate the study of the temporal graph realization pr...
research
∙
01/25/2023
In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
A temporal graph has an edge set that may change over discrete time step...
research
∙
06/26/2022
Hardness of Interval Scheduling on Unrelated Machines
We provide new (parameterized) computational hardness results for Interv...
research
∙
02/24/2022
Counting Temporal Paths
The betweenness centrality of a vertex v is an important centrality meas...
research
∙
02/14/2022
Single Machine Weighted Number of Tardy Jobs Minimization With Small Weights
In this paper we prove new results concerning pseudo-polynomial time alg...
research
∙
02/11/2022
The complexity of computing optimum labelings for temporal connectivity
A graph is temporally connected if there exists a strict temporal path, ...
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
∙
12/27/2021
Equitable Scheduling for the Total Completion Time Objective
We investigate a novel scheduling problem where we have n clients, each ...
research
∙
12/12/2021
Temporal Unit Interval Independent Sets
Temporal graphs have been recently introduced to model changes to a give...
research
∙
07/04/2021
The Complexity of Finding Temporal Separators under Waiting Time Constraints
In this work, we investigate the computational complexity of Restless Te...
research
∙
05/27/2021
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
In static graphs, the betweenness centrality of a graph vertex measures ...
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/18/2021
Interference-free Walks in Time: Temporally Disjoint Paths
We investigate the computational complexity of finding temporally disjoi...
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/09/2020
Equitable Scheduling on a Single Machine
We introduce a natural but seemingly yet unstudied generalization of the...
research
∙
06/15/2020
Algorithmic Aspects of Temporal Betweenness
The betweenness centrality of a graph vertex measures how often this ver...
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
∙
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
∙
09/13/2019
Enumerating Isolated Cliques in Temporal Networks
Isolation has been shown to be a valuable concept in the world of clique...
research
∙
05/13/2019
Computing Maximum Matchings in Temporal Graphs
We study the computational complexity of finding maximum-cardinality tem...
research
∙
11/12/2018
Sliding Window Temporal Graph Coloring
Graph coloring is one of the most famous computational problems with app...
research
∙
10/15/2018
Parameterized Dynamic Cluster Editing
We introduce a dynamic version of the NP-hard Cluster Editing problem. T...
research
∙
06/26/2018
Listing All Maximal k-Plexes in Temporal Graphs
Social networks evolve over time, that is, new contacts appear and old c...
research
∙
05/31/2018
A Parameterized Complexity View on Collapsing k-Cores
We study the NP-hard graph problem Collapsed k-Core where, given an undi...
research
∙
03/01/2018
Temporal Graph Classes: A View Through Temporal Separators
We investigate the computational complexity of separating two distinct v...
research
∙
01/31/2018
Efficient Algorithms for Measuring the Funnel-likeness of DAGs
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funn...
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/04/2017
The Parameterized Complexity of Centrality Improvement in Networks
The centrality of a vertex v in a network intuitively captures how impor...
research
∙
09/26/2017