research
∙
02/01/2023
Parameterized Algorithms for Colored Clustering
In the Colored Clustering problem, one is asked to cluster edge-colored ...
share
research
∙
01/02/2023
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
We provide a general framework to exclude parameterized running times of...
research
∙
08/29/2022
A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners
Contributing to the toolbox for interpreting election results, we evalua...
research
∙
08/02/2022
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
When computing stable matchings, it is usually assumed that the preferen...
research
∙
06/29/2022
There and Back Again: On Applying Data Reduction Rules by Undoing Others
Data reduction rules are an established method in the algorithmic toolbo...
research
∙
05/01/2022
Understanding Distance Measures Among Elections
Motivated by putting empirical work based on (synthetic) election data o...
research
∙
03/31/2022
Finding Balance-Fair Short Paths in Graphs
The computation of short paths in graphs with edge lengths is a pillar o...
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/14/2021
On Improving Resource Allocations by Sharing
Given an initial resource allocation, where some agents may envy others ...
research
∙
12/12/2021
Temporal Unit Interval Independent Sets
Temporal graphs have been recently introduced to model changes to a give...
research
∙
12/10/2021
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Following up on purely theoretical work of Bredereck et al. [AAAI 2020],...
research
∙
12/06/2021
Modification-Fair Cluster Editing
The classic Cluster Editing problem (also known as Correlation Clusterin...
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/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
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Understanding the computational complexity of training simple neural net...
research
∙
05/18/2021
Interference-free Walks in Time: Temporally Disjoint Paths
We investigate the computational complexity of finding temporally disjoi...
research
∙
05/17/2021
Putting a Compass on the Map of Elections
Recently, Szufa et al. [AAMAS 2020] presented a "map of elections" that ...
research
∙
05/14/2021
Optimal Virtual Network Embeddings for Tree Topologies
The performance of distributed and data-centric applications often criti...
research
∙
05/13/2021
Equilibria in Schelling Games: Computational Complexity and Robustness
In the simplest game-theoretic formulation of Schelling's model of segre...
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
∙
02/26/2021
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related ...
research
∙
02/23/2021
A Refined Complexity Analysis of Fair Districting over Graphs
We study the NP-hard Fair Connected Districting problem: Partition a ver...
research
∙
02/17/2021
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Roughly speaking, gerrymandering is the systematic manipulation of the b...
research
∙
11/23/2020
Envy-Free Allocations Respecting Social Networks
Finding an envy-free allocation of indivisible resources to agents is a ...
research
∙
10/19/2020
On the Robustness of Winners: Counting Briberies in Elections
We study the parameterized complexity of counting variants of Swap- and ...
research
∙
10/09/2020
Equitable Scheduling on a Single Machine
We introduce a natural but seemingly yet unstudied generalization of the...
research
∙
09/29/2020
Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the compu...
research
∙
07/09/2020
Line-Up Elections: Parallel Voting with Shared Candidate Pool
We introduce the model of line-up elections which captures parallel or s...
research
∙
07/09/2020
Bribery and Control in Stable Marriage
We initiate the study of external manipulations in Stable Marriage by co...
research
∙
07/02/2020
Approximating Sparse Quadratic Programs
Given a matrix A ∈ℝ^n× n, we consider the problem of maximizing x^TAx su...
research
∙
06/26/2020
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
Editing a graph into a disjoint union of clusters is a standard optimiza...
research
∙
06/15/2020
Algorithmic Aspects of Temporal Betweenness
The betweenness centrality of a graph vertex measures how often this ver...
research
∙
05/11/2020
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Using insights from parametric integer linear programming, we significan...
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
∙
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
∙
02/12/2020
Complexity of Combinatorial Matrix Completion With Diameter Constraints
We thoroughly study a novel and still basic combinatorial matrix complet...
research
∙
02/04/2020
Faster Binary Mean Computation Under Dynamic Time Warping
Many consensus string problems are based on Hamming distance. We replace...
research
∙
02/03/2020
Parameterized Algorithms for Matrix Completion With Radius Constraints
Considering matrices with missing entries, we study NP-hard matrix compl...
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/21/2019
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
We continue and extend previous work on the parameterized complexity ana...
research
∙
10/01/2019
Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomial-time prepocessing...
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
∙
08/30/2019
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Node connectivity plays a central role in temporal network analysis. We ...
research
∙
07/02/2019
Adapting Stable Matchings to Evolving Preferences
Adaptivity to changing environments and constraints is key to success in...
research
∙
06/03/2019