
Most Classic Problems Remain NPhard on Relative Neighborhood Graphs and their Relatives
Proximity graphs have been studied for several decades, motivated by app...
read it

Towards Classifying the PolynomialTime Solvability of Temporal Betweenness Centrality
In static graphs, the betweenness centrality of a graph vertex measures ...
read it

On Finding Separators in Temporal Split and Permutation Graphs
Removing all connections between two vertices s and z in a graph by remo...
read it

The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Understanding the computational complexity of training simple neural net...
read it

Interferencefree Walks in Time: Temporally Disjoint Paths
We investigate the computational complexity of finding temporally disjoi...
read it

Putting a Compass on the Map of Elections
Recently, Szufa et al. [AAMAS 2020] presented a "map of elections" that ...
read it

Optimal Virtual Network Embeddings for Tree Topologies
The performance of distributed and datacentric applications often criti...
read it

Equilibria in Schelling Games: Computational Complexity and Robustness
In the simplest gametheoretic formulation of Schelling's model of segre...
read it

Two Influence Maximization Games on Graphs Made Temporal
To address the dynamic nature of realworld networks, we generalize comp...
read it

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
The NPhard MATERIAL CONSUMPTION SCHEDULING Problem and closely related ...
read it

A Refined Complexity Analysis of Fair Districting over Graphs
We study the NPhard Fair Connected Districting problem: Partition a ver...
read it

The Complexity of Gerrymandering Over Graphs: Paths and Trees
Roughly speaking, gerrymandering is the systematic manipulation of the b...
read it

EnvyFree Allocations Respecting Social Networks
Finding an envyfree allocation of indivisible resources to agents is a ...
read it

On the Robustness of Winners: Counting Briberies in Elections
We study the parameterized complexity of counting variants of Swap and ...
read it

Equitable Scheduling on a Single Machine
We introduce a natural but seemingly yet unstudied generalization of the...
read it

Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the compu...
read it

LineUp Elections: Parallel Voting with Shared Candidate Pool
We introduce the model of lineup elections which captures parallel or s...
read it

Bribery and Control in Stable Marriage
We initiate the study of external manipulations in Stable Marriage by co...
read it

Approximating Sparse Quadratic Programs
Given a matrix A ∈ℝ^n× n, we consider the problem of maximizing x^TAx su...
read it

On 2Clubs in GraphBased Data Clustering: Theory and Algorithm Engineering
Editing a graph into a disjoint union of clusters is a standard optimiza...
read it

Algorithmic Aspects of Temporal Betweenness
The betweenness centrality of a graph vertex measures how often this ver...
read it

HighMultiplicity Fair Allocation Using Parametric Integer Linear Programming
Using insights from parametric integer linear programming, we significan...
read it

As Time Goes By: Reflections on Treewidth for Temporal Graphs
Treewidth is arguably the most important structural graph parameter lead...
read it

Feedback Edge Sets in Temporal Graphs
The classical, lineartime solvable Feedback Edge Set problem is concern...
read it

Multistage st Path: Confronting Similarity with Dissimilarity
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, compr...
read it

Complexity of Combinatorial Matrix Completion With Diameter Constraints
We thoroughly study a novel and still basic combinatorial matrix complet...
read it

Faster Binary Mean Computation Under Dynamic Time Warping
Many consensus string problems are based on Hamming distance. We replace...
read it

Parameterized Algorithms for Matrix Completion With Radius Constraints
Considering matrices with missing entries, we study NPhard matrix compl...
read it

Multistage Graph Problems on a Global Budget
Timeevolving or temporal graphs gain more and more popularity when stud...
read it

Multistage Problems on a Global Budget
Timeevolving or temporal graphs gain more and more popularity when stud...
read it

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

PolynomialTime Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomialtime prepocessing...
read it

Enumerating Isolated Cliques in Temporal Networks
Isolation has been shown to be a valuable concept in the world of clique...
read it

Efficient Computation of Optimal Temporal Walks under WaitingTime Constraints
Node connectivity plays a central role in temporal network analysis. We ...
read it

Adapting Stable Matchings to Evolving Preferences
Adaptivity to changing environments and constraints is key to success in...
read it

Multistage Vertex Cover
Covering all edges of a graph by a minimum number of vertices, this is t...
read it

Computing Maximum Matchings in Temporal Graphs
We study the computational complexity of finding maximumcardinality tem...
read it

Stable Roommates with Narcissistic, SinglePeaked, and SingleCrossing Preferences
The classical Stable Roommates problem asks whether it is possible to ha...
read it

Parameterized Dynamic Cluster Editing
We introduce a dynamic version of the NPhard Cluster Editing problem. T...
read it

Comparing Temporal Graphs Using Dynamic Time Warping
The connections within many realworld networks change over time. Thus, ...
read it

Exact Algorithms for Finding WellConnected 2Clubs in RealWorld Graphs: Theory and Experiments
Finding (maximumcardinality) "cliquish" subgraphs is a central topic in...
read it

On Coalitional Manipulation for Multiwinner Elections: Shortlisting
Shortlisting of candidatesselecting a group of "best" candidatesis a...
read it

Listing All Maximal kPlexes in Temporal Graphs
Social networks evolve over time, that is, new contacts appear and old c...
read it

Data Reduction for Maximum Matching on RealWorld Graphs: Theory and Experiments
Finding a maximumcardinality or maximumweight matching in (edgeweight...
read it

A More FineGrained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
We study the NPhard Shortest Path Most Vital Edges problem arising in t...
read it

Hardness of Consensus Problems for Circular Strings and Time Series Averaging
Consensus problems for strings and sequences appear in numerous applicat...
read it

Temporal Graph Classes: A View Through Temporal Separators
We investigate the computational complexity of separating two distinct v...
read it

Towards Improving Brandes' Algorithm for Betweenness Centrality
Betweenness centrality, measuring how many shortest paths pass through a...
read it

Efficient Algorithms for Measuring the Funnellikeness of DAGs
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funn...
read it

Stable Marriage with MultiModal Preferences
We introduce a generalized version of the famous Stable Marriage problem...
read it
Rolf Niedermeier
is this you? claim profile
Professor of Theoretical Computer Science at Technical University of Berlin