research
∙
07/07/2023
A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
In the Generalized Noah's Ark Problem, one is given a phylogenetic tree ...
share
research
∙
06/07/2023
On Computing Optimal Tree Ensembles
Random forests and, more generally, (decision-)tree ensembles are widely...
research
∙
01/05/2023
Exact and Heuristic Approaches to Speeding Up the MSM Time Series Distance Computation
The computation of the distance of two time series is time-consuming for...
research
∙
11/03/2022
Efficient Branch-and-Bound Algorithms for Finding Triangle-Constrained 2-Clubs
In the Vertex Triangle 2-Club problem, we are given an undirected graph ...
research
∙
09/28/2022
On Computing Exact Means of Time Series Using the Move-Split-Merge Metric
Computing an accurate mean of a set of time series is a critical task in...
research
∙
04/06/2022
Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings
In Bayesian Network Structure Learning (BNSL), one is given a variable s...
research
∙
01/14/2022
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
The s-Club problem asks, for a given undirected graph G, whether G conta...
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
∙
07/09/2021
Preventing Small (𝐬,𝐭)-Cuts by Protecting Edges
We introduce and study Weighted Min (s,t)-Cut Prevention, where we are g...
research
∙
05/20/2021
On the Parameterized Complexity of Polytree Learning
A Bayesian network is a directed acyclic graph that represents statistic...
research
∙
04/29/2021
Parameterized String Equations
We study systems of String Equations where block variables need to be as...
research
∙
04/07/2021
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
We study the computational complexity of c-Colored P_ℓ Deletion and c-Co...
research
∙
03/05/2021
Essentially Tight Kernels for (Weakly) Closed Graphs
We study kernelization of classic hard graph problems when the input gra...
research
∙
01/11/2021
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst...
research
∙
07/10/2020
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
A graph G is weakly γ-closed if every induced subgraph of G contains one...
research
∙
05/08/2020
Exploiting 𝐜-Closure in Kernelization Algorithms for Graph Problems
A graph is c-closed if every pair of vertices with at least c common nei...
research
∙
04/30/2020
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
We study the problem of learning the structure of an optimal Bayesian ne...
research
∙
02/20/2020
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Given an undirected graph G and integers c and k, the Maximum Edge-Color...
research
∙
08/11/2019
Graph Motif Problems Parameterized by Dual
Let G=(V,E) be a vertex-colored graph, where C is the set of colors used...
research
∙
01/11/2019
Destroying Bicolored P_3s by Deleting Few Edges
We introduce and study the Bicolored P_3 Deletion problem defined as fol...
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/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
∙
03/02/2018
On the Relation of Strong Triadic Closure and Cluster Deletion
We study the parameterized and classical complexity of two related probl...
research
∙
10/20/2017