Rolf Niedermeier

research

∙ 02/01/2023

Parameterized Algorithms for Colored Clustering

In the Colored Clustering problem, one is asked to cluster edge-colored ...

0 Leon Kellerhals, et al. ∙

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...

0 Klaus Heeger, et al. ∙

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...

0 Niclas Boehmer, et al. ∙

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...

0 Niclas Boehmer, et al. ∙

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...

0 Aleksander Figiel, et al. ∙

research

∙ 05/01/2022

Understanding Distance Measures Among Elections

Motivated by putting empirical work based on (synthetic) election data o...

0 Niclas Boehmer, et al. ∙

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...

0 Matthias Bentert, et al. ∙

research

∙ 01/14/2022

Delay-Robust Routes in Temporal Graphs

Most transportation networks are inherently temporal: Connections (e.g. ...

0 Eugen Füchsle, et al. ∙

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...

0 Eugen Füchsle, et al. ∙

research

∙ 12/27/2021

Equitable Scheduling for the Total Completion Time Objective

We investigate a novel scheduling problem where we have n clients, each ...

0 Danny Hermelin, et al. ∙

research

∙ 12/14/2021

On Improving Resource Allocations by Sharing

Given an initial resource allocation, where some agents may envy others ...

0 Robert Bredereck, et al. ∙

research

∙ 12/12/2021

Temporal Unit Interval Independent Sets

Temporal graphs have been recently introduced to model changes to a give...

0 Danny Hermelin, et al. ∙

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],...

0 Niclas Boehmer, et al. ∙

research

∙ 12/06/2021

Modification-Fair Cluster Editing

The classic Cluster Editing problem (also known as Correlation Clusterin...

0 Vincent Froese, et al. ∙

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...

0 Pascal Kunz, et al. ∙

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 ...

0 Maciej Rymar, et al. ∙

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...

0 Nicolas Maack, et al. ∙

research

∙ 05/18/2021

The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

Understanding the computational complexity of training simple neural net...

0 Vincent Froese, et al. ∙

research

∙ 05/18/2021

Interference-free Walks in Time: Temporally Disjoint Paths

We investigate the computational complexity of finding temporally disjoi...

0 Nina Klobas, et al. ∙

research

∙ 05/17/2021

Putting a Compass on the Map of Elections

Recently, Szufa et al. [AAMAS 2020] presented a "map of elections" that ...

0 Niclas Boehmer, et al. ∙

research

∙ 05/14/2021

Optimal Virtual Network Embeddings for Tree Topologies

The performance of distributed and data-centric applications often criti...

0 Aleksander Figiel, et al. ∙

research

∙ 05/13/2021

Equilibria in Schelling Games: Computational Complexity and Robustness

In the simplest game-theoretic formulation of Schelling's model of segre...

0 Luca Kreisel, et al. ∙

research

∙ 05/12/2021

Two Influence Maximization Games on Graphs Made Temporal

To address the dynamic nature of real-world networks, we generalize comp...

0 Niclas Boehmer, et al. ∙

research

∙ 02/26/2021

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem

The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related ...

0 Matthias Bentert, et al. ∙

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...

0 Niclas Boehmer, et al. ∙

research

∙ 02/17/2021

The Complexity of Gerrymandering Over Graphs: Paths and Trees

Roughly speaking, gerrymandering is the systematic manipulation of the b...

0 Matthias Bentert, et al. ∙

research

∙ 11/23/2020

Envy-Free Allocations Respecting Social Networks

Finding an envy-free allocation of indivisible resources to agents is a ...

0 Robert Bredereck, et al. ∙

research

∙ 10/19/2020

On the Robustness of Winners: Counting Briberies in Elections

We study the parameterized complexity of counting variants of Swap- and ...

0 Niclas Boehmer, et al. ∙

research

∙ 10/09/2020

Equitable Scheduling on a Single Machine

We introduce a natural but seemingly yet unstudied generalization of the...

0 Klaus Heeger, et al. ∙

research

∙ 09/29/2020

Multidimensional Stable Roommates with Master List

Since the early days of research in algorithms and complexity, the compu...

0 Robert Bredereck, et al. ∙

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...

0 Niclas Boehmer, et al. ∙

research

∙ 07/09/2020

Bribery and Control in Stable Marriage

We initiate the study of external manipulations in Stable Marriage by co...

0 Niclas Boehmer, et al. ∙

research

∙ 07/02/2020

Approximating Sparse Quadratic Programs

Given a matrix A ∈ℝ^n× n, we consider the problem of maximizing x^TAx su...

0 Danny Hermelin, et al. ∙

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...

0 Aleksander Figiel, et al. ∙

research

∙ 06/15/2020

Algorithmic Aspects of Temporal Betweenness

The betweenness centrality of a graph vertex measures how often this ver...

0 Sebastian Buß, et al. ∙

research

∙ 05/11/2020

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

Using insights from parametric integer linear programming, we significan...

0 Robert Bredereck, et al. ∙

research

∙ 04/28/2020

As Time Goes By: Reflections on Treewidth for Temporal Graphs

Treewidth is arguably the most important structural graph parameter lead...

0 Till Fluschnik, et al. ∙

research

∙ 03/30/2020

Feedback Edge Sets in Temporal Graphs

The classical, linear-time solvable Feedback Edge Set problem is concern...

0 Roman Haag, et al. ∙

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...

0 Till Fluschnik, et al. ∙

research

∙ 02/12/2020

Complexity of Combinatorial Matrix Completion With Diameter Constraints

We thoroughly study a novel and still basic combinatorial matrix complet...

0 Tomohiro Koana, et al. ∙

research

∙ 02/04/2020

Faster Binary Mean Computation Under Dynamic Time Warping

Many consensus string problems are based on Hamming distance. We replace...

0 Nathan Schaar, et al. ∙

research

∙ 02/03/2020

Parameterized Algorithms for Matrix Completion With Radius Constraints

Considering matrices with missing entries, we study NP-hard matrix compl...

0 Tomohiro Koana, et al. ∙

research

∙ 12/09/2019

Multistage Graph Problems on a Global Budget

Time-evolving or temporal graphs gain more and more popularity when stud...

0 Klaus Heeger, et al. ∙

research

∙ 12/09/2019

Multistage Problems on a Global Budget

Time-evolving or temporal graphs gain more and more popularity when stud...

0 Klaus Heeger, et al. ∙

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...

0 Robert Bredereck, et al. ∙

research

∙ 10/01/2019

Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions

Kernelization is the fundamental notion for polynomial-time prepocessing...

0 Matthias Bentert, et al. ∙

research

∙ 09/13/2019

Enumerating Isolated Cliques in Temporal Networks

Isolation has been shown to be a valuable concept in the world of clique...

0 Hendrik Molter, et al. ∙

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 ...

0 Anne-Sophie Himmel, et al. ∙

research

∙ 07/02/2019

Adapting Stable Matchings to Evolving Preferences

Adaptivity to changing environments and constraints is key to success in...

0 Robert Bredereck, et al. ∙

research

∙ 06/03/2019

Multistage Vertex Cover

Covering all edges of a graph by a minimum number of vertices, this is t...

0 Till Fluschnik, et al. ∙

Rolf Niedermeier

Featured Co-authors