research
∙
09/01/2023
The Complexity of Cluster Vertex Splitting and Company
Clustering a graph when the clusters can overlap can be seen from three ...
share
research
∙
06/07/2023
On Computing Optimal Tree Ensembles
Random forests and, more generally, (decision-)tree ensembles are widely...
research
∙
12/01/2022
Game Implementation: What Are the Obstructions?
In many applications, we want to influence the decisions of independent ...
research
∙
10/13/2022
Threshold Treewidth and Hypertree Width
Treewidth and hypertree width have proven to be highly successful struct...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
05/16/2022
The Influence of Dimensions on the Complexity of Computing Decision Trees
A decision tree recursively splits a feature space ℝ^d and then assigns ...
research
∙
03/07/2022
Turbocharging Heuristics for Weak Coloring Numbers
Bounded expansion and nowhere-dense classes of graphs capture the theore...
research
∙
02/24/2022
Planarizing Graphs and their Drawings by Vertex Splitting
The splitting number of a graph G=(V,E) is the minimum number of vertex ...
research
∙
05/12/2021
On (Coalitional) Exchange-Stable Matching
We study (coalitional) exchange stability, which Alcalde [Economic Desig...
research
∙
03/15/2021
Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
research
∙
11/24/2020
Fractional Matchings under Preferences: Stability and Optimality
We thoroughly study a generalized version of the classic Stable Marriage...
research
∙
09/27/2020
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
The notion of forbidden-transition graphs allows for a robust generaliza...
research
∙
08/05/2020
Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
research
∙
05/31/2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
research
∙
03/05/2020
Optimal Discretization is Fixed-parameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
research
∙
02/04/2020
A Double Exponential Lower Bound for the Distinct Vectors Problem
In the (binary) Distinct Vectors problem we are given a binary matrix A ...
research
∙
10/18/2019
Cluster Editing parameterized above the size of a modification-disjoint P_3 packing is para-NP-hard
Given a graph G=(V,E) and an integer k, the Cluster Editing problem asks...
research
∙
07/04/2019
Packing directed circuits quarter-integrally
The celebrated Erdős-Pósa theorem states that every undirected graph tha...
research
∙
02/15/2019
Matchings under Preferences: Strength of Stability and Trade-offs
We propose two solution concepts for matchings under preferences: robust...
research
∙
11/23/2018
Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Given an undirected graph G=(V,E) the NP-hard Strong Triadic Closure (ST...
research
∙
08/27/2018
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
A fundamental graph problem is to recognize whether the vertex set of a ...
research
∙
07/24/2018
A Note on Clustering Aggregation
We consider the clustering aggregation problem in which we are given a s...
research
∙
07/17/2018
On Computing Centroids According to the p-Norms of Hamming Distance Vectors
In this paper we consider the p-Norm Hamming Centroid problem which asks...
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/06/2017
Computational Complexity Aspects of Point Visibility Graphs
A point visibility graph is a graph induced by a set of points in the pl...
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
A Parameterized View on Multi-Layer Cluster Editing
In classical Cluster Editing we seek to transform a given graph into a d...
research
∙
07/13/2017