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...
share
research
∙
12/14/2022
Correlating Theory and Practice in Finding Clubs and Plexes
Finding large "cliquish" subgraphs is a classic NP-hard graph problem. I...
research
∙
11/13/2022
Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
Given a graph and two integers k and ℓ, Partial Vertex Cover asks for a ...
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
∙
01/14/2022
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
We study the following two fixed-cardinality optimization problems (a ma...
research
∙
12/14/2021
Combating Collusion Rings is Hard but Possible
A recent report of Littmann [Commun. ACM '21] outlines the existence and...
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
∙
07/24/2020
Using a geometric lens to find k disjoint shortest paths
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1...
research
∙
07/23/2020
Detecting and Enumerating Small Induced Subgraphs in c-Closed Graphs
Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called c-clo...
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
∙
05/29/2020
Parameterized Complexity of Min-Power Asymmetric Connectivity
We investigate parameterized algorithms for the NP-hard problem Min-Powe...
research
∙
10/01/2019
Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomial-time prepocessing...
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
∙
10/15/2018
Parameterized Dynamic Cluster Editing
We introduce a dynamic version of the NP-hard Cluster Editing problem. T...
research
∙
07/19/2018
Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments
Finding (maximum-cardinality) "cliquish" subgraphs is a central topic in...
research
∙
06/25/2018
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
Finding a maximum-cardinality or maximum-weight matching in (edge-weight...
research
∙
04/24/2018
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
We study the NP-hard Shortest Path Most Vital Edges problem arising in t...
research
∙
02/27/2018
Parameterized Complexity of Diameter
Diameter--the task of computing the length of a longest shortest path---...
research
∙
02/19/2018
Towards Improving Brandes' Algorithm for Betweenness Centrality
Betweenness centrality, measuring how many shortest paths pass through a...
research
∙
10/20/2017